Interleaving String Problem Solution

Interleaving String Problem: Given strings s1s2, 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];
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment