# Is there a trick here or are we supposed to convert a recursion to a for loop?

• It's quite easy to solve it using recursion but the result is "Time Limit Exceeded" on some very long input.
I can convert the recursion to a for loop, but it's quite tedious and I feel I'm missing the whole point of the question.
Is there some kind of a trick here?

• It depends. Do you consider dynamic programming a trick?

• Following is my solution that can AC, actually it is a dynamic programming code:

``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
if(len3 != len1 + len2)return false;
bool res[len1 + 1][len2 + 1];
res[0][0] = true;
for(int i = 1; i <= len2; i++)res[0][i] = s2.substr(0, i) == s3.substr(0, i);
for(int i = 1; i <= len1; i++)res[i][0] = s1.substr(0, i) == s3.substr(0, i);
for(int i = 1; i <= len1; i++)
for(int j = 1; j <= len2; j++){
res[i][j] = (s3[i + j - 1] == s1[i - 1] && res[i - 1][j]) ||
(s3[i + j - 1] == s2[j - 1] && res[i][j - 1]);

}

return res[len1][len2];
}
};
``````

res[i][j] indicates whether s3.substr(0, i + j) is the interleaving string of s1.substr(0, i) and s2.substr(0, j). The transmitting function is res[i][j] = (s3[i + j - 1] == s1[i - 1] && res[i - 1][j]) ||
(s3[i + j - 1] == s2[j - 1] && res[i][j - 1]); So, res[len1][len2] is the finally result.

• Do you think recursion and for-loop has the same complexity? You may share these 2 code to make people find the real reason.

• Recursion or for-loop is not the key-point. I also wrote a for-loop and it still report that time exceeds. here is my code:

``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int i1 = 0, i2 = 0, i3 = 0;
if (s1.length() + s2.length() != s3.length() )
{
return false;
}
else
{
if (s1 == s3) return true;
if (s2 == s3) return true;
}
return isInterleave(s1, i1, s2, i2, s3, i3);
}
bool isInterleave(string s1, int i1, string s2, int i2, string s3, int i3) {
stack<int> s;
bool ret = true;
while(i1 + i2 < s3.length())
{
if (s1[i1] == s3[i3] && s2[i2] != s3[i3])
{
i1++;
i3++;
}
else if (s1[i1] != s3[i3] && s2[i2] == s3[i3])
{
i2++;
i3++;
}
else if (s1[i1] == s3[i3] && s2[i2] == s3[i3])
{
s.push(i1);
s.push(i2);
s.push(i3);
i1++;
i3++;
}
else if (!s.empty())
{
i3 = s.top();
s.pop();

i2 = s.top();
s.pop();

i1 = s.top();
s.pop();

/* take the untaken path */
i2++;
i3++;
}
else
{
ret = false;
break;
}
}
return ret;
}
};``````

• This post is deleted!

• Thank you for the hint.

I read this interesting page:

http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming

Then I implemented it and worked out.
I just used stl containers to cache results.
Passed.

• My DP solution with O(S1 * S2) time complex and O(max(S1, S2)) space complex, AC in 16ms:

``````bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size())
return false;
if (s1.size() < s2.size())
s1.swap(s2);
vector<bool>  dp(s1.size() + 1);
for (size_t j = 0; j <= s2.size(); ++j){
dp[0] = (!j || (dp[0] && s2[j - 1] == s3[j - 1]));
for (size_t i = 1; i <= s1.size(); ++i)
dp[i] = ((dp[i - 1] && s1[i - 1] == s3[i + j - 1]) || (j > 0 && dp[i] && s2[j - 1] == s3[i + j - 1]));
}
return dp.back();
}``````

• Very beautiful~

• Brilliant!! guy

• can you explain why you have to swap the string please?

• I also cannot understand why you need to swap s1 and s2 to get large size dp[]? acturally, the value in dp might be wrong, for example, when i = 0, j=2, your temporary result in dp always get dp[0] = ture, this is incorrect, but why your final result is still right?

• Ok, you catch me!
I reviewed my solution and found a mistake, which generate wrong answer when s1="a", s2=“b" and s3="aa". So I modified it, now it should be right.
Talking about the swap of s1 and s2, I just want to make fewer iterations for the outer loop, which I think may improve the code locality.
Thank you for the eagle eyes!

• This post is deleted!

• This post is deleted!

• Hi, firstly I have figured out the recursion solution just like you, and obviously get TLE. Then I realize the recursive solution solve sub problems again and again, which indicates DP is a better solution. But I don't want give up my recursion code (and too lazy to work out a DP solution).

So, based on the original code I added a Map to cache the result of every sub problem. When to solve a problem, we first lookup the Map; once we get result, we put it into the Map. This cache way works like a charm. After all, the key of DP is to cache intermediate results, which the Map in my case does the same job.

• Recursive Solution with cache can AC

``````public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()){
return false;
}

Map<String, Boolean> cache = new HashMap<>();
return isInterleave(s1.toCharArray(), 0, s2.toCharArray(), 0, s3.toCharArray(), cache);
}

boolean isInterleave(char[] a1, int i, char[] a2, int j, char[] a3, Map<String, Boolean> cache) {
if(i == a1.length && j == a2.length){
return true;
}else if(i == a1.length){
return isSame(a2, j, a3, i + j);
}else if(j == a2.length){
return isSame(a1, i, a3, i + j);
}

char c1 = a1[i];
char c2 = a2[j];

String k1 = (i + 1) + ":" + j;
String k2 = i + ":" + (j + 1);

if(c1 != a3[i + j] && c2 != a3[i + j]){
return false;
}

if(c1 == a3[i + j]){
if(!cache.containsKey(k1)){
cache.put(k1, isInterleave(a1, i + 1, a2, j, a3, cache));
}

if(cache.get(k1)){
return true;
}
}

//c2 == a3[i + j]
if(!cache.containsKey(k2)){
cache.put(k2, isInterleave(a1, i, a2, j + 1, a3, cache));
}

return cache.get(k2);
}

private boolean isSame(char[] a1, int i, char[] a2, int j){
for(int k = 0; k + i < a1.length; k++){
if(a1[i + k] != a2[j + k]){
return false;
}
}

return true;
}
}``````

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