Wildcard Matching

Share

Given input string s and pattern p with ? and * support, implement wildcard matching. ? matches any single character, * matches any sequence (including empty).

Example 1
Input: s="aa", p="a" → Output: false
Example 2
Input: s="adceb", p="*a*b" → Output: true

Solution Approach

DP: dp[i][j] = whether s[0..i-1] matches p[0..j-1]. For *, dp[i][j] = dp[i-1][j] (use one char) || dp[i][j-1] (match empty).

  • dp[0][0]=true; dp[0][j]=true if all p[0..j-1] are *.
  • If p[j-1]==* : dp[i][j] = dp[i-1][j] || dp[i][j-1].
  • If p[j-1]==? or matches s[i-1]: dp[i][j] = dp[i-1][j-1].
Java
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++) dp[0][j] = dp[0][j-1] && p.charAt(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-1][j] || dp[i][j-1];
                else if (p.charAt(j-1) == '?' || p.charAt(j-1) == s.charAt(i-1)) dp[i][j] = dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(M*N)