Wildcard Matching - Leetcode Solution

The Wildcard Matching problem on Leetcode asks for an algorithm to determine if a given string s matches a given pattern p, where the pattern includes the special characters '?' (matching any single character) and '*' (matching any sequence of characters, including an empty sequence).

To solve this problem, we can use dynamic programming with a two-dimensional boolean array dp, where dp[i][j] represents whether the first i characters of s match the first j characters of p. The base case is dp[0][0] = True, because an empty string matches an empty pattern.

For each i from 0 to the length of s, we iterate through each j from 0 to the length of p, and update dp[i][j] based on the following cases:

1. If p[j-1] is a non-special character, we require that s[i-1] and p[j-1] match exactly, so dp[i][j] = dp[i-1][j-1] and s[i-1] == p[j-1].

2. If p[j-1] is a '?' character, we can match any single character, so dp[i][j] = dp[i-1][j-1].

3. If p[j-1] is a '*' character, we can either match zero characters (dp[i][j-1]) or match one or more characters (dp[i-1][j]) in s. Therefore, dp[i][j] = dp[i-1][j] or dp[i][j-1].

The final result is dp[length of s][length of p], which represents whether the entire s matches the entire p.

Here is the Python implementation of the solution:

def isMatch(s: str, p: str) -> bool: dp = [[False](len(p)+1) for _ in range(len(s)+1)] dp[0][0] = True for j in range(1, len(p)+1): if p[j-1] == '': dp[0][j] = dp[0][j-1] for i in range(1, len(s)+1): for j in range(1, len(p)+1): if p[j-1] != '*': dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '?') else: dp[i][j] = dp[i-1][j] or dp[i][j-1] return dp[len(s)][len(p)]

The time complexity of this solution is O(len(s) * len(p)), and the space complexity is also O(len(s) * len(p)) due to the dp array.

1