Three solutions: recursion, recursion with memory, and DP. Hope this post can help you. :D


  • 0
    Z

    Recursion is time limit exceeted if there are two many the same letters in s1 and s2. Hence we can keep those ways we have tried to save a lot of time. Many DP problems can be solved using recursion with memory.

    recursion solution:

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            if (s1.size() + s2.size() != s3.size()) return false;
            return isInterleave(s1, s2, s3, 0, 0);
        }
        bool isInterleave(string &s1, string &s2, string &s3, int a, int b) {
            if (s1.empty() && s2.empty() && s3.empty()) return true;
            if (s1.size() == a && s2.size() == b) return true;
            if (s1.size() == a) {
                if (s2[b] != s3[a+b]) return false;
                else return isInterleave(s1, s2, s3, a, b+1);
            }
            if (s2.size() == b) {
                if (s1[a] != s3[a+b]) return false;
                else return isInterleave(s1, s2, s3, a+1, b);
            }
            if (s1[a] == s3[a+b] && isInterleave(s1, s2, s3, a+1, b)) return true;
            if (s2[b] == s3[a+b] && isInterleave(s1, s2, s3, a, b+1)) return true;
            else return false;
        }
    };
    

    recursion with memory:

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            if (s1.size() + s2.size() != s3.size()) return false;
            if (s1.empty() && s2.empty() && s3.empty()) return true;
            vector<bool> v(s2.size()+1, false);
            vector<vector<bool>> keep(s1.size()+1, v);
            return isInterleave(s1, s2, s3, 0, 0, keep);
        }
        bool isInterleave(string &s1, string &s2, string &s3, int a, int b, vector<vector<bool>>& keep) {
            if (keep[a][b]) return false;
            keep[a][b] = true;
            if (s1.size() == a && s2.size() == b) return true;
            if (s1.size() == a) {
                if (s2[b] != s3[a+b]) return false;
                else return isInterleave(s1, s2, s3, a, b+1, keep);
            }
            if (s2.size() == b) {
                if (s1[a] != s3[a+b]) return false;
                else return isInterleave(s1, s2, s3, a+1, b, keep);
            }
            if (s1[a] == s3[a+b] && isInterleave(s1, s2, s3, a+1, b, keep)) return true;
            if (s2[b] == s3[a+b] && isInterleave(s1, s2, s3, a, b+1, keep)) return true;
            else return false;
        }
    };
    

    DP solution:

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            if (s1.size() + s2.size() != s3.size()) return false;
            if (s1.empty()) return s2 == s3;
            if (s2.empty()) return s1 == s3;
            bool dp[s1.size()+1][s2.size()+1];
            dp[0][0] = true;
            for (int i = 1; i <= s1.size(); ++i) {
                if (dp[i-1][0] && s1[i-1] == s3[i-1]) dp[i][0] = true;
                else dp[i][0] = false;
            }
            for (int j = 1; j <= s2.size(); ++j) {
                if (dp[0][j-1] && s2[j-1] == s3[j-1]) dp[0][j] = true;
                else dp[0][j] = true;
            }
            for (int i = 1; i <= s1.size(); ++i) {
                for (int j = 1; j <= s2.size(); ++j) {
                    if ((dp[i-1][j] && s1[i-1] == s3[i+j-1]) || (dp[i][j-1] && s2[j-1] == s3[i+j-1]))
                        dp[i][j] = true;
                    else dp[i][j] = false;
                }
            }
            return dp[s1.size()][s2.size()];
        }
    };>! Spoiler

Log in to reply
 

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