8ms backtracking solution C++

• ``````//regular expression matching
//first solution: using recursive version
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
return backtracking(s, m, p, n);
}

bool backtracking(string& s, int i, string& p, int j) {
if (i == 0 && j == 0) return true;
if (i != 0 && j == 0) return false;
if (i == 0 && j != 0) {
//in this case only p == "c*c*c*" this pattern can match null string
if (p[j-1] == '*') {
return backtracking(s, i, p, j-2);
}
return false;
}
//now both i and j are not null
if (s[i-1] == p[j-1] || p[j-1] == '.') {
return backtracking(s, i - 1, p, j - 1);
} else if (p[j-1] == '*') {
//two cases: determines on whether p[j-2] == s[i-1]
//first p[j-2]* matches zero characters of p
if (backtracking(s, i, p, j - 2)) return true;
//second consider whether p[j-2] == s[i-1], if true, then s[i-1] is matched, move to backtracking(i - 1, j)
if (p[j-2] == s[i-1] || p[j-2] == '.') {
return backtracking(s, i - 1, p, j);
}
return false;
}
return false;
}
};``````

• my DFS solution which takes 700ms, I hava no idea why it runs so slowly?

``````bool isMatch(string s, string p) {
bool res = false;
backTrack(s,p, 0, 0, res);

return res;
}
void backTrack(string s, string p, int posOfS, int posOfP, bool& res){
///< 类似于剪枝函数，既然有一个路径走通了，知道可以匹配了，所以其他的就可以直接返回了
if(res == true) return;///< 一旦有一个路径可以找到，大家都回家
///< 如果s与p可以同时走完全程，那么我们就认为找到路径了
if(posOfS==s.size() && posOfP==p.size()){
res=true;  ///< 如果能够两个字符串都可以走完，走到桥的另一头，也就是找到路le
return;
}else if(posOfP==p.size()){
return;    ///< 如果p率先走完全程，另一个不陪他玩了。。。
}else if(posOfS==s.size()){
while(posOfP<p.size()-1 && (p[posOfP]!='*' && p[posOfP+1]=='*')){
posOfP+=2;
}
if(posOfP==p.size()){
res=true;
}
return;
}

if(posOfP<p.size()-1 && p[posOfP+1]=='*'){
backTrack(s,p,posOfS,posOfP+2,res);
if(s[posOfS]==p[posOfP] || p[posOfP]=='.'){
backTrack(s,p,posOfS+1,posOfP,res);
}
}else{
if(p[posOfP]==s[posOfS] || p[posOfP]=='.'){
backTrack(s,p,posOfS+1,posOfP+1,res);
}
}
}``````

• your explanation is truly clear and brief . 3Q very much!
And, by using DFS, we exactly avoid reviewing a character repeatedly, in which way we will have the same time complexity with dynamic programming!

• (1) If you change the backTrack defination to this:
void backTrack(string& s, string& p, int posOfS, int posOfP, bool& res)

The runtime will be 156ms.

(2) I believe that this line:
if(res == true) return;///< 一旦有一个路径可以找到，大家都回家
cannot ensure once a pattern match is found, the dfs solution process (which is a tree structure process) exit globally, maybe you still need to set the res value as the return value of backTrack() function, in this way, in these lines:

``````if(posOfP<p.size()-1 && p[posOfP+1]=='*'){
backTrack(s,p,posOfS,posOfP+2,res);
if(s[posOfS]==p[posOfP] || p[posOfP]=='.'){
backTrack(s,p,posOfS+1,posOfP,res);
}
``````

You can judge whether the return value is true, if it's true, exit. (In this way, you can exit from the dfs solution tree globally).

I have optimized your code to 136ms (however, I cannot optimize it any more):

``````class Solution {
public:
bool isMatch(string s, string p) {
//bool res = false;
return backTrack(s,p, 0, 0);

// return res;
}
bool backTrack(string& s, string& p, int posOfS, int posOfP){
///< 类似于剪枝函数，既然有一个路径走通了，知道可以匹配了，所以其他的就可以直接返回了
///< 如果s与p可以同时走完全程，那么我们就认为找到路径了
if(posOfS==s.size() && posOfP==p.size()){
return true;  ///< 如果能够两个字符串都可以走完，走到桥的另一头，也就是找到路le
}else if(posOfP==p.size()){
return false;    ///< 如果p率先走完全程，另一个不陪他玩了。。。
}else if(posOfS==s.size()){
while(posOfP<p.size()-1 && (p[posOfP]!='*' && p[posOfP+1]=='*')){
posOfP+=2;
}
if(posOfP==p.size()){
return true; //res=true;
}
return false;
}

if(posOfP<p.size()-1 && p[posOfP+1]=='*'){
if ( backTrack(s,p,posOfS,posOfP+2) ) return true; //add judge condition
if(s[posOfS]==p[posOfP] || p[posOfP]=='.'){
return backTrack(s,p,posOfS+1,posOfP);
}
return false;
}else{
if(p[posOfP]==s[posOfS] || p[posOfP]=='.'){
return backTrack(s,p,posOfS+1,posOfP+1);
}
return false;
}
}
};
``````

• No problem! Thanks you!

• I have a questions, there are a few places have the potential of overflow, and there is not condition check such as for (j - 2 >= 0) for p[j - 2], however, it seems that it can be compiled without problem. What is the reason behind it?
e.g. if s = "", p="*"

• @Ximin.Z It's because we assume the test case is right, we do not consider the case like:

s = "aaaaa", p = "*"

because it's invalid.

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