Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

一刷
题解：

• 表示长度为0或n的任意字符串
  ？表示any character

  
  

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

有一种constant space的解法留给二刷

二刷：二维DP

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