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


  • 0
    A

    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?


  • 0
    L

    It depends. Do you consider dynamic programming a trick?


  • 25
    Q

    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.


  • 0
    S

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


  • 0
    R

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

  • 0
    G
    This post is deleted!

  • 0
    R

    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.


  • 4
    W

    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();
    }

  • 0
    D

    Very beautiful~


  • 0
    W

    Brilliant!! guy


  • 0
    S

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


  • 0
    L

    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?


  • 0
    W

    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!


  • 0
    N
    This post is deleted!

  • 0
    N
    This post is deleted!

  • 0
    N

    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.


  • 0
    D

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

Log in to reply
 

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