dynamic_programming.wildcard_matching

Author : ilyas dahhou Date : Oct 7, 2023

Task: Given an input string and a pattern, implement wildcard pattern matching with support for ‘?’ and ‘*’ where: ‘?’ matches any single character. ‘*’ matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial).

Runtime complexity: O(m * n)

The implementation was tested on the leetcode: https://leetcode.com/problems/wildcard-matching/

Functions

is_match(→ bool)

Module Contents

dynamic_programming.wildcard_matching.is_match(string: str, pattern: str) → bool

>>> is_match("", "")
True
>>> is_match("aa", "a")
False
>>> is_match("abc", "abc")
True
>>> is_match("abc", "*c")
True
>>> is_match("abc", "a*")
True
>>> is_match("abc", "*a*")
True
>>> is_match("abc", "?b?")
True
>>> is_match("abc", "*?")
True
>>> is_match("abc", "a*d")
False
>>> is_match("abc", "a*c?")
False
>>> is_match('baaabab','*****ba*****ba')
False
>>> is_match('baaabab','*****ba*****ab')
True
>>> is_match('aa','*')
True