# Recursive C++ works, but I don't know why

• I started with a straight forward recursive algorithm that basically does DFS (branching point at the [2 matches] case in the code, where s1 and s2 has the same first characters) and it got TLE.
After some struggling, I made a small modification to the DFS, that is instead of advancing 1 character, I made it advance till the character changes. The code got accepted (5-12ms), and I dont know why lol, since the complexity should be basically the same.

``````class Solution {
public:
bool isInterleave(const string & s1, const string & s2, const string & s3, int p1 = 0, int p2 = 0, int p3 = 0) {

while (true)
{
// done
if (p1 == s1.length() && p2 == s2.length() && p3 == s3.length())
return true;

// 2 matches
else if (p1 < s1.length() && p2 < s2.length() && p3 < s3.length() && s1[p1] == s3[p3] && s2[p2] == s3[p3])
{
// choose s1
for (int i = 0; true; i++)
if (!(p1 + i < s1.length() && p3 + i < s3.length() && s1[p1 + i] == s1[p1] && s3[p3 + i] == s1[p1]))
{   // insert i character from s1 to s3, so advance p1 and p3 by i
// check if this choice is correct
if (isInterleave(s1, s2, s3, p1+i, p2, p3+i))
return true;
break;
}

// choose s2
for (int i = 0; true; i++)
if (!(p2 + i < s2.length() && p3 + i < s3.length() && s2[p2 + i] == s1[p1] && s3[p3 + i] == s1[p1]))
{   // insert i character from s2 to s3, so advance p2 and p3 by i
if (isInterleave(s1, s2, s3, p1, p2+i, p3+i))
return true;
break;
}

// both 2 choices don't work
return false;
}
// 1 matches
else if (p1 < s1.length() && p3 < s3.length() && s1[p1] == s3[p3])
{
p1++;
p3++;
}
else if (p2 < s2.length() && p3 < s3.length() && s2[p2] == s3[p3])
{
p2++;
p3++;
}
// no match
else
return false;
}

}
};``````

• I think the recursive solution does not re use the results of sub problems already calculated unless you use memiozation. The same thing happened to me and I changed my solution to normal DP w/o recursion and it worked like a charm.

• This post is deleted!

• I use recursition and got wrong answer because I cant figure out in case of two match, but I didnt consider to compare only same substring.

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