C++ 6ms DP+Backtracking solution

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

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