# my backtracking solution (9ms c++)

• ``````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;
}
};
``````

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