wildcard_matching.py

"""
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/
"""


defis_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
 """
dp= [[False] * (len(pattern) +1) for_instring+"1"]
dp[0][0] =True
# Fill in the first row
forj, charinenumerate(pattern, 1):
ifchar=="*":
dp[0][j] =dp[0][j-1]
# Fill in the rest of the DP table
fori, s_charinenumerate(string, 1):
forj, p_charinenumerate(pattern, 1):
ifp_charin (s_char, "?"):
dp[i][j] =dp[i-1][j-1]
elifpattern[j-1] =="*":
dp[i][j] =dp[i-1][j] ordp[i][j-1]
returndp[len(string)][len(pattern)]


if__name__=="__main__":
importdoctest

doctest.testmod()
print(f"{is_match('baaabab','*****ba*****ab') =}")