# Verbose case by case recursion solution C++ 6ms

• ``````class Solution
{
public:
bool isMatch(string a, string b){
return rec(a, a.size() - 1, b, b.size() - 1);
// scan from right to left, since '*' only process leftward chars
}

bool rec(string& a, int ia, string& b, int ib){
if (ia == -1 && ib == -1)
return true;
if (ia == -1){
if (b[ib] == '*'){
return rec(a, ia, b, ib - 2);  // for cases :   [], [c*c*]
}
return false;
}
if (ib == -1)
return rec(b, ib, a, ia);

if (a[ia] != '*' && b[ib] != '*')
return (a[ia] == '.' || b[ib] == '.' || a[ia] == b[ib]) && rec(a, ia - 1, b, ib - 1);

if (a[ia] == '*' && b[ib] == '*'){
if (a[ia - 1] == b[ib - 1])
return rec(a, ia - 2, b, ib - 2);
else
return rec(a, ia, b, ib - 2) || rec(a, ia - 2, b, ib);
}

if (a[ia] == '*')
return rec(b, ib, a, ia);

//if (b[ib] == '*'){
char rep = b[ib - 1];

if (rep != '.'){
bool tmp = false;
for (; ia >= -1 && a[ia] == rep; --ia){  // for case: [aaa], [a*b*a*], you cannot simply skip all 'a', you have to check position one by one.
tmp |= rec(a, ia, b, ib - 2);
if (tmp)
return true;
}
return rec(a, ia, b, ib - 2);
}
else{
bool tmp = false;
for (; ia >= -1; --ia){		// for case: [aaa], [.*]. Here [.*] means [....] which can mean any equivalently long strings.
tmp |= rec(a, ia, b, ib - 2);
if (tmp)
return true;
}
return false;
}
//	}
}
};
``````

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