Problem

Wildcard Matching

Approach

  1. It frist comes to my mind that we can use DFS to work this out. However, I get a TLE. After analysing these test data, I realize that the time complexity is 2^min(N, M)
  2. So, there is DP. Let dp[i][j] means whether the string is matched, in which the first one is s[:i + 1] and the second is t[:j + 1]. And,
    • if s[i] == p[j], dp[i][j] = dp[i - 1][j - 1]
    • if p[j] == ‘?’, dp[i][j] = dp[i - 1][j - 1], it means the i-th char matches the j-th char.
    • if p[j] == ‘’, dp[i][j] = dp[i - 1][j](the i-th char is matched by ‘’ and the ‘*’ could match more) dp[i - 1][j - 1](the i-th char is matched by ‘’ and the ‘’ won’t match more) dp[i][j - 1](the ‘*’ match nothing)

Code

class Solution {
    public boolean isMatch(String s, String p) {
        int N = s.length(), M = p.length();
        boolean[][] dp = new boolean[N + 1][M + 1];
        dp[0][0] = true;
        if(M > 0 && p.charAt(0) == '*'){
            int id = 0;
            while(id < M && p.charAt(id) == '*'){
                dp[0][id + 1] = true;
                id ++;
            }
        }
        for(int i = 1; i <= N; i ++){
            char chOfS = s.charAt(i - 1);
            for(int j = 1; j <= M; j ++){
                char chOfP = p.charAt(j - 1);
                if((chOfS == chOfP || chOfP == '?') && dp[i - 1][j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                }
                if(chOfP == '*'){
                    if(dp[i - 1][j - 1] || dp[i][j - 1] || dp[i - 1][j]){
                        dp[i][j] = true;
                    }
                }
            }
         }
        return dp[N][M];
    }
}