C++ recursive solution with memoization


  • 0
    I

    recursive solution is rather straightforward based on geeksforgeeks solution - http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings-set-2/
    I've added memoization table so that we can avoid calculating the same result again.

    // T[i][j] represents the result for s1 with ith index and s2 with jth index
    bool isInterleave(string s1, string s2, string s3, vector<vector<int>>& T, int i, int j) {
        if (s1.size() == 0 && s2.size() == 0 && s3.size() == 0) return true;
    
        bool first = false, second = false;
        if (T[i][j] == -1) {
            if (s1.size() && s1[0] == s3[0]) {
                first = isInterleave(s1.substr(1), s2, s3.substr(1), T, i+1, j);
                T[i][j] = first;
            }
            if (first) return true;
            if (s2.size() && s2[0] == s3[0]) {
                second = isInterleave(s1, s2.substr(1), s3.substr(1), T, i, j+1);
                T[i][j] = second;
            }
        }
        return T[i][j] == 1;
    }
    
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size()+ s2.size() != s3.size()) return false;
        // add 1 so we have minimum 1 for empty string to avoid runtime error
        vector<vector<int>> T(s1.size()+1, vector<int>(s2.size()+1, -1));
        return isInterleave(s1,s2,s3,T,0,0);
    }

Log in to reply
 

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