题解 | #通配符匹配#

此题目和链接NC 122 正则表达式匹配有点类似，但两者的动态规划的递推式是有区别的。

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        string str(s);
        string pattern(p);
        return ismatch(str, p);
    }
    
    bool ismatch(string s, string p){
        if(p.empty()){
            return s.empty();
        }
        
        int m = s.length(), n = p.length();
        vector<vector<bool>> dp(m+1, vector<bool>(n+1));
        dp[0][0] = true;
        
        for(int i=1; i<=n; i++){
            if(p[i-1] == '*'){
                dp[0][i] = true;
            }
            else{
                break;
            }
        }
        
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(s[i-1] == p[j-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];
                }
            }
        }
        return dp[m][n];
    }
    
};