# Why recursion works one-way?

• hi, guys,

The following code is working:

``````    public class Solution {
public boolean isInterleave(String s1, String s2, String s) {
return isInterleave(s1, s1.length()-1, s2, s2.length()-1, s, s.length()-1);
}

public boolean isInterleave(String s1, int i1, String s2, int i2, String s, int i){
if(i<0){
if(i1<0 && i2<0) return true;
else    return false;
}

if(i1 >= 0 && s1.charAt(i1)==s.charAt(i) && isInterleave(s1,i1-1,s2,i2,s,i-1))
return true;

if(i2 >= 0 && s2.charAt(i2)==s.charAt(i) && isInterleave(s1,i1,s2,i2-1,s,i-1))
return true;
return false;
}
}
``````

But when I tried recursion from the head, time limit exceeded:

``````    public class Solution {
public boolean isInterleave(String s1, String s2, String s) {
return isInterleave(s1, 0, s2, 0, s, 0);
}

public boolean isInterleave(String s1, int i1, String s2, int i2, String s, int i){
if(i>=s.length()){
if(i1>=s1.length() && i2>=s2.length()) return true;
else    return false;
}

if(i1 < s1.length() && s1.charAt(i1)==s.charAt(i) && isInterleave(s1,i1+1,s2,i2,s,i+1))
return true;

if(i2 < s2.length() && s2.charAt(i2)==s.charAt(i) && isInterleave(s1,i1,s2,i2+1,s,i+1))
return true;
return false;
}
}
``````

I just feel they are totally equivalent.

Do someone have an idea? Thanks!

• Could you please update your post with the correct code format? Select all code, then click `{}` button. And also, try to explain the algorithm more detail.

• Yes, these 2 code totally same, should both get Time Limit Exceeded.

However, it seems a weakness of test case in OJ.

• I think Dynamic Programing can be a better way to solve this question.

• Why do you think Dynamic Programing can be a better way to solve this question?

• Running backwards has less `s.length()` invocations.

• Anyhow, both got me "Time Limit Exceeded"

• A[i][j] represents "s[0...i+j-1] is interleaves of s1[0...i-1] and s2[0...j-1]
so, you can calculate all elements of A, in O(mn).
And the final result is A[m][n]

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