Interleaved Strings

Given strings A, B, and C, find whether C is formed by an interleaving of A and B.

An interleaving of two strings S and T is a configuration such that it creates a new string Y from the concatenation substrings of A and B and |Y| = |A + B| = |C|

For example:

• A = “XYZ”
• B = “ABC”

so we can make multiple interleaving string Y like, XYZABC, XAYBCZ, AXBYZC, XYAZBC and many more so here your task is to check whether you can create a string Y which can be equal to C.

Specifically, you just need to create substrings of string A and create substrings B and concatenate them and check whether it is equal to C or not.

Note: a + b is the concatenation of strings a and b.

Return true if C is formed by an interleaving of A and B, else return false.

• Time : O(nm)

• Space : O(min(n,m))

• bottom up dp optimization2

class Solution {
public:
    /*You are required to complete this method */
    bool isInterleave(string A, string B, string C) {
        int n = A.length(), m = B.length();
        if(n + m != C.length()) return false;
        if(n < m) return isInterleave(B, A, C);
        vector<bool> dp(m + 1);
        dp[0] = true;
        bool possible = true;
        for(int i = 0; i <= n and possible; i++) {
            possible = false;
            for(int j = 0; j <= m; j++) {
                if(!dp[j]) continue;
                int pos = i + j;
                if(pos == C.length()) break;
                if(i < n and C[pos] == A[i]) possible = true;
                else dp[j] = false;
                if(j < m and C[pos] == B[j]) dp[j+1] = true;
            }
        }
        return dp.back();
    }
};

• Time : O(nm)

• Space : O(m)

• bottom up dp optimization

class Solution {
public:
    /*You are required to complete this method */
    bool isInterleave(string A, string B, string C) {
        int n = A.length(), m = B.length();
        if(n + m != C.length()) return false;
        vector<bool> dp(m + 1);
        dp[0] = true;
        bool possible = true;
        for(int i = 0; i <= n and possible; i++) {
            vector<bool> ndp(m + 1);
            possible = false;
            for(int j = 0; j <= m; j++) {
                if(!dp[j]) continue;
                int pos = i + j;
                if(i < n and C[pos] == A[i]) possible = ndp[j] = true;
                if(j < m and C[pos] == B[j]) dp[j+1] = true;
            }
            if(i != n) swap(dp, ndp);
        }
        return dp.back();
    }
};

• Time : O(nm)

• Space : O(nm)

• bottom up dp

class Solution {
    vector<vector<bool>> dp;
public:
    /*You are required to complete this method */
    bool isInterleave(string A, string B, string C) {
        int n = A.length(), m = B.length();
        if(n + m != C.length()) return false;
        dp = vector<vector<bool>>(n + 1, vector<bool>(m + 1));
        dp[0][0] = true;
        for(int i = 0; i <= n and !dp[n][m]; i++) {
            for(int j = 0; j <= m and !dp[n][m]; j++) {
                if(!dp[i][j]) continue;
                int pos = i + j;
                if(i < n and C[pos] == A[i]) dp[i+1][j] = true;
                if(j < m and C[pos] == B[j]) dp[i][j+1] = true;
            }
        }
        return dp[n][m];
    }
};

• Time : O(nm)

• Space : O(nm)

• top down dp

class Solution {
    vector<vector<bool>> dp;
    bool helper(string& A, string& B, string& C, int i, int j) {
        if(i + j == C.length()) return true;
        if(dp[i][j]) return false;
        dp[i][j] = true;
        int n = A.length(), m = B.length();
        if(i < n and A[i] == C[i + j] and helper(A,B,C,i+1,j)) return true;
        if(j < m and B[j] == C[i + j] and helper(A,B,C,i,j+1)) return true;
        return false;
    }
public:
    /*You are required to complete this method */
    bool isInterleave(string A, string B, string C) {
        int n = A.length(), m = B.length();
        if(n + m != C.length()) return false;
        dp = vector<vector<bool>>(n + 1, vector<bool>(m + 1));
        return helper(A,B,C,0,0);
    }
};