Why recursion works one-way?


  • 0
    C

    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!


  • 0
    S

    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.


  • 3
    S

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

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


  • 1
    U

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


  • 0
    A

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


  • 0
    A

    Running backwards has less s.length() invocations.


  • 0
    A

    Anyhow, both got me "Time Limit Exceeded"


  • 0
    U

    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]


Log in to reply
 

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