Easy Understanding Recursive Back Search, C++

• ``````class Solution {
public:
bool isMatch(string s, string p) {
input_string = s;
match_string = p;
return is_match(s.length()-1, p.length()-1);
}

bool is_match(int i, int j) {
// i,j both finised, matching return true
if (i==-1 && j==-1) return true;
// i remains, but j finished, then false
if (i!=-1 && j==-1) return false;
// i finished, but j remians, check if j is *.
if (i==-1 && j!=-1){
// if i is 0, when j is *, then directly use * as 0
if (match_string[j]=='*'){
return is_match(i,j-2);
}else{
return false;
}
}
if (input_string[i]==match_string[j] || match_string[j]=='.'){
return is_match(i-1,j-1);
}else{
if (match_string[j]=='*'){
// if j is * and j -1 match i. use * or not use *
if (match_string[j-1] == input_string[i] || match_string[j-1] == '.'){
//     not use *          use * again
return is_match(i,j-2)  || is_match(i-1,j);
}else{
// if j is * and j-1 not matching i, not use *
return is_match(i,j-2);
}
}else{
// if not * and not matching then, return false
return false;
}
}
}

string input_string, match_string;
};
``````

Key point is, in each iteration whenever uses *, it can use it 0 times or multiple times.
When use 0 times, directly jump 2 characters in the matching string

``````is_match(i,j-2)
``````

When uses multiple times (include 1 time), stay at current position

``````is_match(i-1, j)
``````

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