Ddsszz

Ghpc.cpp

bool isAsterisk(char c){
    return c == '*';
}
bool isQuestion(char c){
    return c == '?';
}
bool isMatchSymbol(char s, char m){
    return isQuestion(m) || s == m;
}
int Solution::isMatch(const string source, const string mask) {  
    int S = source.length();
    int M = mask.length();
    vector<bool> dp(S + 1, false);
    dp[S] = true;    
    for(int m = M - 1; m >= 0; m--){       
        vector<bool> newDp(S + 1, false);
        if(isAsterisk(mask[m]))
            newDp[S] = dp[S];
        for(int s = S - 1; s >= 0; s--){
            if(isAsterisk(mask[m])){
                newDp[s] = dp[s] || dp[s + 1] || newDp[s + 1];
            } else {
                newDp[s] = dp[s + 1] && isMatchSymbol(source[s], mask[m]);
            }
        }
        dp = newDp;
    } 
    return dp[0];
}