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