44. Wildcard Matching 


Given an input string (s) and a pattern (p), 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).

 

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".


To implement wildcard pattern matching, we can use a dynamic programming approach. We can create a 2D boolean array dp where dp[i][j] represents whether the substring of s from index 0 to index i-1 matches the substring of p from index 0 to index j-1.

Initially, dp[0][0] will be true because the empty string matches the empty string. Then, we can fill in the first row and first column of the array as follows:

For the first row, dp[0][j] will be true if and only if p[j-1] is '' and dp[0][j-1] is true. This is because '' can match the empty string, so if the previous character of p was '*' and the previous substring of p matched the empty string, then the current substring of p will also match the empty string.

For the first column, dp[i][0] will be false for all i greater than 0. This is because the empty string can never match a non-empty string.

Once we have filled in the first row and first column, we can fill in the rest of the array using the following rules:

1. If s[i-1] and p[j-1] are the same character or if p[j-1] is '?', then dp[i][j] will be true if and only if dp[i-1][j-1] is true. This is because the current character of s will match the current character of p if and only if the previous characters of s and p matched.

2. If p[j-1] is '', then dp[i][j] will be true if and only if dp[i][j-1] or dp[i-1][j] is true. This is because '' can match any sequence of characters, so it will match the current character of s if the previous characters of s and p matched, or it will match the empty string if the previous characters of p matched the current substring of s.

3. Once we have filled in the entire array, we can return the value of dp[m][n], where m is the length of s and n is the length of p. This will be true if and only if the entire string s matches the pattern p.


Here is some example code that implements this algorithm:

def isMatch(s: str, p: str) -> bool:
    # m and n are the lengths of s and p, respectively.
    m, n = len(s), len(p)
    
    # Create the 2D boolean array dp.
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # Initially, dp[0][0] is true because the empty string matches the empty string.
    dp[0][0] = True
    
    # Fill in the first row of dp.
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            # If the previous character of p was '*', then


This code implements a dynamic programming solution to the wildcard pattern matching problem. It takes as input a string s and a pattern p and returns whether s matches p according to the rules of wildcard pattern matching.

The code first initializes two variables m and n to the lengths of s and p, respectively. It then creates a 2D boolean array dp where dp[i][j] represents whether the substring of s from index 0 to index i-1 matches the substring of p from index 0 to index j-1.

Next, the code sets dp[0][0] to true because the empty string matches the empty string. It then fills in the first row of dp using the rules described above: if p[j-1] is '*' and dp[0][j-1] is true, then dp[0][j] will be true.

After filling in the first row, the code fills in the rest of the array using the rules described above: if s[i-1] and p[j-1] are the same character or if p[j-1] is '?', then dp[i][j] will be true if and only if dp[i-1][j-1] is true. If p[j-1] is '*', then dp[i][j] will be true if and only if dp[i][j-1] or dp[i-1][j] is true.

Finally, the code returns the value of dp[m][n], which will be true if and only if the entire string s matches the pattern p.


as '*', then