Code Implementation

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n+1) for _ in range(m+1)]
        dp[0][0] = True

        # Only '*' can match with empty string
        for j in range(1, n+1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-1]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if p[j-1] == '*':
                    # '*' matches zero (dp[i][j-1]) or one/more (dp[i-1][j])
                    dp[i][j] = dp[i][j-1] or dp[i-1][j]
                elif p[j-1] == '?' or s[i-1] == p[j-1]:
                    dp[i][j] = dp[i-1][j-1]
        return dp[m][n]
      

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
        dp[0][0] = true;
        for (int j = 1; j <= n; ++j)
            if (p[j-1] == '*')
                dp[0][j] = dp[0][j-1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j-1] == '*')
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                else if (p[j-1] == '?' || s[i-1] == p[j-1])
                    dp[i][j] = dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};
      

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int j = 1; j <= n; ++j)
            if (p.charAt(j-1) == '*')
                dp[0][j] = dp[0][j-1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j-1) == '*')
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                else if (p.charAt(j-1) == '?' || s.charAt(i-1) == p.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}
      

var isMatch = function(s, p) {
    const m = s.length, n = p.length;
    const dp = Array.from({length: m+1}, () => Array(n+1).fill(false));
    dp[0][0] = true;
    for (let j = 1; j <= n; ++j)
        if (p[j-1] === '*')
            dp[0][j] = dp[0][j-1];
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (p[j-1] === '*')
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            else if (p[j-1] === '?' || s[i-1] === p[j-1])
                dp[i][j] = dp[i-1][j-1];
        }
    }
    return dp[m][n];
};
      

Problem Description

Given two strings, s (the input string) and p (the pattern), determine if s matches the pattern p. The pattern may include the wildcard characters:

• '?' – matches any single character.
• '*' – matches any sequence of characters (including the empty sequence).

Thought Process

At first glance, the problem seems similar to regular expression matching, but with only '?' and '*' as special characters. A brute-force approach would try all possible ways to match '*' to zero or more characters, which quickly becomes infeasible for long strings due to exponential possibilities.

To optimize, we notice that for each position in s and p, the result depends only on the decisions made previously. This property is ideal for dynamic programming (DP), where we can store and reuse results of subproblems. By using a DP table to keep track of matches between all prefixes of s and p, we can avoid redundant computations and efficiently solve the problem.

Solution Approach

We'll use a two-dimensional dynamic programming (DP) table where dp[i][j] is true if the first i characters of s match the first j characters of p.

1. Initialization:
   • dp[0][0] is true since an empty pattern matches an empty string.
   • For dp[0][j] (empty string vs pattern), only possible if all previous pattern characters are '*' (since '*' can represent empty).
2. Filling the DP Table:
   • If p[j-1] is '*': We have two choices:
     • Treat '*' as matching zero characters: dp[i][j-1]
     • Treat '*' as matching one or more characters: dp[i-1][j]
     So, dp[i][j] = dp[i][j-1] || dp[i-1][j].
   • If p[j-1] is '?' or matches s[i-1]: dp[i][j] = dp[i-1][j-1]
   • Otherwise, dp[i][j] = false.
3. Result:
   • The answer is dp[m][n], where m and n are the lengths of s and p, respectively.

This approach ensures that we only process each subproblem once, leading to efficient performance.

Example Walkthrough

Let's consider s = "adceb" and p = "*a*b".

1. Initialization:
   • dp[0][0] = true
   • Since p[0] is '*', dp[0][1] = true
   • Rest of dp[0][j] are false
2. DP Table Filling:
   • For each i and j, fill according to rules above.
   • For p[0] ('*'), dp[1][1] = dp[1][0] || dp[0][1], and so on.
   • When p[1] is 'a', dp[1][2] checks if s[0] is 'a' (it is), so dp[1][2] = dp[0][1].
   • Continue for all positions.
3. Final Result:
   • dp[5][4] = true, so the function returns true.

This step-by-step filling ensures we consider all possible ways '*' can match sequences, and '?' matches single characters.

Time and Space Complexity

• Brute-force: Exponential time O(2^{m+n}) due to trying all ways '*' can expand.
• Optimized DP:
  • Time Complexity: O(mn) where m and n are the lengths of s and p, since we fill each cell of the DP table once.
  • Space Complexity: O(mn) for the DP table. (Can be optimized to O(n) with rolling arrays.)

Summary

Wildcard Matching is a classic dynamic programming problem. By recognizing overlapping subproblems and using a DP table to store intermediate results, we efficiently handle the complexity introduced by the '*' wildcard. The approach is systematic and avoids redundant computation, making it both elegant and practical for large inputs.