Wildcard Matching (Leetcode 44)

个人感觉这道题的dp递归方程比regular expression那道题要容易很多。
dp[i][j] 为 i-1为结尾的string s 与 j-1 为结尾的string p是否match，则有以下公式：

dp[i][j] = dp[i-1][j-1] => if s[i-1] == s[j-1] or p[j-1] = '?'
dp[i][j] = dp[i-1][j-1] || dp[i-1][j] || dp[i][j-1] => if p[i-1] = '*'

class Solution {
public:
    bool isMatch(string s, string p) {
        if(s.empty() && p.empty()) return true;
        int lens = s.length(), lenp = p.length();
        vector<vector<bool>> dp(lens+1, vector<bool>(lenp+1));
        dp[0][0] = true;
        
        for(int i=0; i<=lens; i++){
            if(i == 0){
                for(int j=1; j<=lenp; j++){
                    if(p[j-1] == '*') dp[0][j] = dp[0][j-1];
                }
            }else{
                //dp[i][0] = 0;
                for(int j=1; j<=lenp; j++){
                    if(p[j-1] == '?' || s[i-1] == p[j-1]){
                        dp[i][j] = dp[i-1][j-1];
                    }else if(p[j-1] == '*'){
                        dp[i][j] = (dp[i-1][j] || dp[i][j-1] || dp[i-1][j-1]);
                    }/*else{
                        dp[i][j] = 0;
                    }*/
                }
            }
        }
        return dp[lens][lenp];
    }
};

如果要求follow up为减少空间复杂度 （时间复杂度就应该用双指针来做了），则应该使用滚动数组。使用滚动数组时，切记取mod的方法有一个问题：就是会重用第i-2行的值，所以一定要记得清零（若条件不满足）。注意两段代码的不同之处

class Solution {
public:
    bool isMatch(string s, string p) {
        if(s.empty() && p.empty()) return true;
        int lens = s.length(), lenp = p.length();
        vector<vector<bool>> dp(2, vector<bool>(lenp+1));
        dp[0][0] = true;
        
        for(int i=0; i<=lens; i++){
            if(i == 0){
                for(int j=1; j<=lenp; j++){
                    if(p[j-1] == '*') dp[0][j] = dp[0][j-1];
                }
            }else{
                dp[i%2][0] = 0;
                for(int j=1; j<=lenp; j++){
                    if(p[j-1] == '?' || s[i-1] == p[j-1]){
                        dp[i%2][j] = dp[(i-1)%2][j-1];
                    }else if(p[j-1] == '*'){
                        dp[i%2][j] = (dp[(i-1)%2][j] || dp[i%2][j-1] || dp[(i-1)%2][j-1]);
                    }else{
                        dp[i%2][j] = 0;
                    }
                }
            }
        }
        return dp[lens%2][lenp];
    }
};