C++ 6ms DP+Backtracking solution


  • 0
    B

    Backtracking is the driving algorithm, DP technique is just used to record and save the time to find out.

    class Solution {
        vector<vector<int>> dp;
        // if match return true;
        bool matching(const string &s, const string &p, int nexts, int nextp) {
            if (dp[nexts][nextp] == 0 || dp[nexts][nextp] == 1)
                return dp[nexts][nextp];
        
            if (nexts == s.size() && nextp == p.size()) {
                dp[nexts][nextp] = 1;
                return true;
            }
            if (nextp == p.size()) {
                dp[nexts][nextp] = 0;
                return false;
            }
            if (nexts == s.size()) {
                if (nextp+1 < p.size() && p[nextp+1] == '*') {
                    if (matching(s, p, nexts, nextp+2)) {
                        return true;
                    }
                }
                return false;
            }
            if (nextp+1 < p.size() && p[nextp+1] == '*') {
                if (p[nextp] == '.' || p[nextp] == s[nexts]) {
                    if (matching(s, p, nexts+1, nextp)) 
                        return true;
                    if (matching(s, p, nexts+1, nextp+2)) 
                        return true;
                }
                if (matching(s, p, nexts, nextp+2)) 
                    return true;
            }
            else {
                if (p[nextp] == '.' || p[nextp] == s[nexts]) {
                    if (matching(s, p, nexts+1, nextp+1)) 
                    return true;
                }
            }
            dp[nexts][nextp] = 0;
            return false;
        }
    public:
        bool isMatch(string s, string p) {
            //if (s == "aaaaaaaaaaaaab" && p =="a*a*a*a*a*a*a*a*a*a*c")
            //    return false;
            dp.assign(s.size()+1, vector<int>(p.size()+1, -1)); // -1 is not init, 0 not match, 1 match
            return matching(s, p, 0, 0);
        }
    };
    

Log in to reply
 

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