my backtracking solution (9ms c++)


  • 0
    W
    class Solution {
    public:
        bool isMatch(string s, string p) {
            if(p.empty()){
                if(!s.empty()) return false;
                return true;
            }
            vector<int> dp(p.size(), -1);
            return helper(s, p, dp, 0, -1);
        }
    private:
        bool helper(const string& s, const string& p, vector<int>& dp, int k, int pre){
            for(; k<p.size(); ++k){
                if(k<p.size()-1&&p[k+1]=='*'){
                    dp[k]=-1;
                    dp[++k]=-1;
                    continue;
                }
                break;
            }
            if(k>=p.size()){
                return helper_2(s, p, dp);
            }
            for(int i=pre+1; i<s.size(); ++i){
                if(p[k]=='.'||s[i]==p[k]){
                    dp[k]=i;
                    if(helper(s, p, dp, k+1, i)) return true;
                }
            }
            return false;
        }
        bool helper_2(const string& s, const string& p, vector<int>& dp){
            int start_s=-1, end_s=-1, start_p=-1, end_p=-1;
            for(int i=0; i<dp.size();){
                if(dp[i]==-1){
                    if(i==0) start_s=0;
                    else start_s=dp[i-1]+1;
                    start_p = i;
                    while(i<dp.size()&&dp[i]==-1) ++i;
                    if(i==dp.size()) end_s = s.size()-1;
                    else end_s = dp[i]-1;
                    end_p = i-1;
                    if(!helper_3(s, p, start_s, end_s, start_p, end_p)) return false;
                }else
                    ++i;
            }
            for(int i=0; i<dp.size(); ++i){
                if(i==0&&dp[i]>0) return false;
                else if(i==dp.size()-1&&dp[i]<s.size()-1&&dp[i]!=-1) return false;
                if(i<dp.size()-1&&dp[i]!=-1&&dp[i+1]!=-1&&dp[i+1]-dp[i]>1) return false;
            }
            return true;
        }
        bool helper_3(const string& s, const string& p, int start_s, int end_s, int start_p, int end_p){
            int i, j;
            for(i=start_s, j=start_p; i<=end_s&&j<=end_p;j+=2){
                if(p[j]=='.') return true;
                for(;i<=end_s&&s[i]==p[j];++i)
                    ;
            }
            if(i>end_s) return true;
            return false;
        }
    };
    

Log in to reply
 

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