9ms DP solution with clear steps and cases


  • 0
    E
    class Solution {
    public:
        bool isMatch(string s, string p) {
            vector<vector<bool>> T(s.size()+1, vector<bool>(p.size()+1, false)); // All "false" by default
            T[0][0] = true; // if both strings are empty result is "true"
            for(int j = 2; j <= p.size(); j++) { // The s is empty but p has at least two characters
                if(p[j-1] == '*') T[0][j] = T[0][j-2];
            }
            for(int i = 1; i <= s.size(); i++) { // i == 0 was handled so start at 1
                for(int j = 1; j <= p.size(); j++) { // j == 0 was handled so start at 1
                    if(p[j-1] == '.' || p[j-1] == s[i-1]) T[i][j] = T[i-1][j-1]; // Simple case: characters match or p has '.'
                    else if(p[j-1] == '*') { // complicated case: p has '*'
                        if(T[i][j-2]) T[i][j] = T[i][j-2]; // '*' and its preceding char. match with 0 chars in s
                        else if(s[i-1] == p[j-2] || p[j-2] == '.') T[i][j] = T[i-1][j]; //Preceding char match the current char in s
                    }
                }
            }
            return T[s.size()][p.size()];
        }
    };
    
    

Log in to reply
 

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