Interleaving String Problem Solution

Interleaving String Problem: Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Interleaving String Problem Solution

Problem Solution In Python

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        found = False
        memo = set()
        def interleave(i,j):
            nonlocal memo, s1, s2, s3, found
            if (i,j) in memo:
                return 
            if found: return
            
            if i == len(s1)-1 and j == len(s2)-1:
                found = True
            k = i+j+2
            memo.add((i,j))

            if i+1 < len(s1) and s1[i+1] == s3[k]:
                interleave(i+1, j)
            
            if j+1 < len(s2) and s2[j+1] == s3[k]:
                interleave(i,j+1)
            
        interleave(-1,-1)
        return found

Problem Solution In Java

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length() != s3.length()) return false;
        char[] a1 = s1.toCharArray();
        char[] a2 = s2.toCharArray();
        char[] a3 = s3.toCharArray();
        int[][] dp = new int[a1.length+1][a2.length+1];
        
        return helper(a1, a2,a3,0,0,0,dp);
    }
    boolean helper(char[] a1, char[] a2, char[] a3, int i1, int i2, int i3, int[][] dp) {
        if(i1==a1.length && i2==a2.length && i3==a3.length) return true;
        
        if(dp[i1][i2]!=0) return false;
        
        if(i1<a1.length && a1[i1]==a3[i3] ) {
            if(helper(a1, a2, a3, i1+1, i2, i3+1,dp)) return true;
           
        }
        if(i2<a2.length && a2[i2]==a3[i3]){
            if(helper(a1, a2, a3, i1, i2+1, i3+1, dp)) return true;
        }
        dp[i1][i2]=1;
        
        return false;
    }
}

Problem Solution In C++

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int M, N;
        M = s1.length();
        N = s2.length();
        
        if (s3.length() != M + N)
            return false;
    
        bool T[M+1][N+1];

        T[0][0] = true;

        for (int j = 1; j <= N; ++j)
            T[0][j] = T[0][j-1] && s2[j-1] == s3[j-1];

        for (int i = 1; i <= M; ++i)
            T[i][0] = T[i-1][0] && s1[i-1] == s3[i-1];
        
        for (int i = 1; i <= M; ++i)
            for (int j = 1; j <= N; ++j)
                T[i][j] = (T[i-1][j] && s1[i-1] == s3[i+j-1] ) || (T[i][j-1] && s2[j-1] == s3[i+j-1] );
        
        return T[M][N];
    }
};

Problem Solution In C

bool dp[1010];
bool isInterleave(char* s1, char* s2, char* s3) {
    int aLen = strlen(s1), bLen = strlen(s2), cLen = strlen(s3);
    if(aLen + bLen != cLen) return false;
    dp[0] = true;
    for(int j = 1; j <= bLen; j++)
        dp[j] = dp[j - 1] && (s2[j - 1] == s3[j - 1]);
    for(int i = 1; i <= aLen; i++){
        char cur = s1[i - 1];
        dp[0] = dp[0] && (s1[i - 1] == s3[i - 1]);
        for(int j = 1; j <= bLen; j++)
            dp[j] = (dp[j] && cur == s3[i + j - 1]) || (dp[j - 1] && s2[j - 1] == s3[i + j - 1]);
    }
    return dp[bLen];
}