DP solution in c++


  • 0
    S

    As topic

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

  • 0
    S
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.