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 om n the implementation was tested on the leetcode https leetcode comproblemswildcardmatching ismatch true ismatchaa a false ismatchabc abc true ismatchabc c true ismatchabc a true ismatchabc a true ismatchabc b true ismatchabc true ismatchabc ad false ismatchabc ac false ismatch baaabab baba false ismatch baaabab baab true ismatch aa true fill in the first row fill in the rest of the dp table 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 fill in the first row fill in the rest of the dp table
def is_match(string: str, pattern: str) -> bool:
    
    dp = [[False] * (len(pattern) + 1) for _ in string + "1"]
    dp[0][0] = True
    
    for j, char in enumerate(pattern, 1):
        if char == "*":
            dp[0][j] = dp[0][j - 1]
    
    for i, s_char in enumerate(string, 1):
        for j, p_char in enumerate(pattern, 1):
            if p_char in (s_char, "?"):
                dp[i][j] = dp[i - 1][j - 1]
            elif pattern[j - 1] == "*":
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
    return dp[len(string)][len(pattern)]


if __name__ == "__main__":
    import doctest

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