# 0ms using recursion without dp

• Here is my idea:

1. Our goal is to cut the "head" (same chars at the beginning) in s3 until it's empty. e.g.: when `s3="aabcc"`, the first step is to cut off `"aa"`, then `b`and`"cc"`.
2. When we do this, we must make sure we have the same sub-string in `s1, s2` and cut them off.

`count()`is used to count the number of char same as `s3[0]`, and then we do the analysis step by step. During each recursion, we must cut off the head in `s3`with the same char, so we always have `s3.substr(numS3, s3.size() - numS3)`when we call the next recursion.

1. `if (s1.size() + s2.size() != s3.size())return false;`
`if (!s3.size())return true;`
These is obvious.
2. `if (numS1 + numS2 < numS3) return false;`
e.g.: `s1="ab", s2="ab",s3="aaab";`There is no enough`a`in`s1,s2`to cut off in `s3`.
3. `if (numS1 + numS2 == numS3)`
woudourful, cut all of them.
4. `if (numS1 > numS3)` or `if (numS2 > numS3)`
e.g.: `s1="aaa", s2="ab",s3="aabaa";`, When`aa`is cut off in`s3`, we have to cut two`a`within`s1,s2`. It will be fail at the next step if we cut`aa`in`s1`. So we must cut`s2`first.
5. At last, a normal recursion. Note that we have to choose cut all of the head in`s1`or in`s2`.

It may be a little redundant. But I'm going to post here, because I think it is helpful to speed up when the head is long.
It's still would possible to have the same case recursion and solve repeatedly. So it can be improved by employing dp.

C++:

``````class Solution {
private:
//	count chars same as the first char
int count(string s, char first) {
unsigned int num = 0;
while (num < s.size() && s[num] == first)num++;
return num;
}
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size())return false;
if (!s3.size())return true;

int numS1 = count(s1, s3[0]);
int numS2 = count(s2, s3[0]);
int numS3 = count(s3, s3[0]);

//	special cases
if (numS1+numS2<numS3)	return false;
if (numS1 > numS3&&numS2 > numS3)	return false;
if (numS1 + numS2 == numS3)	return isInterleave(s1.substr(numS1,s1.size()-numS1),s2.substr(numS2,s2.size()-numS2),s3.substr(numS3,s3.size()-numS3));
if (numS1 == 0) return isInterleave(s1, s2.substr(numS3, s2.size() - numS3), s3.substr(numS3, s3.size() - numS3));
if (numS2 == 0) return isInterleave(s1.substr(numS3, s1.size() - numS3), s2, s3.substr(numS3, s3.size() - numS3));
if (numS1 > numS3) return isInterleave(s1.substr(numS3-numS2,s1.size()-(numS3 - numS2)), s2.substr(numS2,s2.size()-numS2), s3.substr(numS3,s3.size()-numS3));
if (numS2 > numS3) return isInterleave(s1.substr(numS1, s1.size() - numS1), s2.substr(numS3 - numS1, s2.size() - (numS3 - numS1)), s3.substr(numS3, s3.size() - numS3));

return isInterleave(s1.substr(numS3 - numS2, s1.size() - (numS3 - numS2)), s2.substr(numS2, s2.size() - numS2), s3.substr(numS3, s3.size() - numS3))
|| isInterleave(s1.substr(numS1, s1.size() - numS1), s2.substr(numS3 - numS1, s2.size() - (numS3 - numS1)), s3.substr(numS3, s3.size() - numS3));
}
};
``````

• a little change

``````class Solution {
private:

//	count chars same as the first one
int count(string s, int base, char first) {
unsigned int num = 0;
while (base + num < s.size() && s[base + num] == first)num++;
return num;
}
bool isInterleaveAux(string s1, unsigned int base1, string s2, unsigned int base2, string s3, unsigned int base3) {
if (base1 > s1.size() || base2 > s2.size())	return false;
if (base3==s3.size())	return true;

int numS1 = count(s1, base1, s3[base3]);
int numS2 = count(s2, base2, s3[base3]);
int numS3 = count(s3, base3, s3[base3]);

//	special cases
if (numS1 + numS2 < numS3)	return false;
if (numS1 > numS3&&numS2 > numS3)	return false;
//	cut s1&s2
if (numS1 + numS2 == numS3)	return isInterleaveAux(s1, base1 + numS1, s2, base2 + numS2, s3, base3 + numS3);

//	Note that now numS1+numS2>numS3
//	cut the one has
if (numS1 == 0) return isInterleaveAux(s1, base1, s2, base2 + numS3, s3, base3 + numS3);
if (numS2 == 0) return isInterleaveAux(s1, base1 + numS3, s2, base2, s3, base3 + numS3);
//	cut all the one less
if (numS1 > numS3) return isInterleaveAux(s1, base1 + numS3 - numS2, s2, base2 + numS2, s3, base3 + numS3);
if (numS2 > numS3) return isInterleaveAux(s1, base1 + numS1, s2, base2 + numS3 - numS1, s3, base3 + numS3);

//	cut all one of them
return isInterleaveAux(s1, base1 + numS3 - numS2, s2, base2 + numS2, s3, base3 + numS3)
|| isInterleaveAux(s1, base1 + numS1, s2, base2 + numS3 - numS1, s3, base3 + numS3);
}
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size())	return false;
return	isInterleaveAux(s1, 0, s2, 0, s3, 0);
}
};
``````

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