Here, We see Interleaving String LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Interleaving String LeetCode Solution

Problem Statement

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

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

An interleaving of two strings s and t is a configuration where s and t are divided into n and m

substrings respectively, such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

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

Interleaving String Leetcode Solution C++

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size();
        int n2 = s2.size();
        int n3 = s3.size();
        
        if(n3 == 0) return true;
        
        if(n1+n2 != n3) return false; 
        
        int dp[n1+1][n2+1];
        memset(dp, 0, sizeof(dp));
        
        for(int i=0; i<=n1; i++){
            for(int j=0; j<=n2; j++){
                if(i == 0 && j == 0) //both strings are empty so it is interleaving
                    dp[i][j] = 1;
                
                else if(i == 0){ //s1 is empty
                    if(s2[j-1] == s3[j-1])
                        dp[i][j] = dp[i][j-1];
                }
                
                else if(j == 0){ // s2 is empty
                    if(s1[i-1] == s3[i-1])
                        dp[i][j] = dp[i-1][j];
                }
                
                else if(s1[i-1] != s3[i+j-1] && s2[j-1] == s3[i+j-1]) //if not match with s1
                    dp[i][j] = dp[i][j-1];
                
                else if(s1[i-1] == s3[i+j-1] && s2[j-1] != s3[i+j-1])   //if not match with s2
                    dp[i][j] = dp[i-1][j];
                
                else if(s1[i-1] == s3[i+j-1] && s2[j-1] == s3[i+j-1])  // If match with both s1 and s2
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
            }
        }      
        return dp[n1][n2];
        
    }
};Code language: PHP (php)

Interleaving String Leetcode Solution Java

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        char[] c1 = s1.toCharArray(), c2 = s2.toCharArray(), c3 = s3.toCharArray();
	int m = s1.length(), n = s2.length();
	if(m + n != s3.length()) return false;
	return dfs(c1, c2, c3, 0, 0, 0, new boolean[m + 1][n + 1]);
}

public boolean dfs(char[] c1, char[] c2, char[] c3, int i, int j, int k, boolean[][] invalid) {
	if(invalid[i][j]) return false;
	if(k == c3.length) return true;
	boolean valid = 
	    i < c1.length && c1[i] == c3[k] && dfs(c1, c2, c3, i + 1, j, k + 1, invalid) || 
        j < c2.length && c2[j] == c3[k] && dfs(c1, c2, c3, i, j + 1, k + 1, invalid);
	if(!valid) invalid[i][j] = true;
    return valid;    
    }
}Code language: JavaScript (javascript)

Interleaving String Leetcode Solution JavaScript

var isInterleave = function(s1, s2, s3) {
    const dp = new Map();
    const solve = (a = 0, b = 0, c = 0) => {
        if(c == s3.length) return a == s1.length && b == s2.length;
        const key = [a, b, c].join(':');
        
        if(dp.has(key)) {
            // console.log('hit');
            return dp.get(key);
        }
        
        let takeS1 = false, takeS2 = false;
        if(s1[a] == s3[c]) takeS1 = solve(a + 1, b, c + 1);
        if(s2[b] == s3[c]) takeS2 = solve(a, b + 1, c + 1);

        dp.set(key, takeS1 || takeS2);
        return takeS1 || takeS2;
    }
    return solve();   
};Code language: JavaScript (javascript)

Interleaving String Leetcode Solution Python

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        if len(s1)==0:
            return s2==s3
        elif len(s2)==0:
            return s1==s3
        elif len(s3)==0:
            return 0==len(s1)+len(s2)
        elif len(s3)!=len(s1)+len(s2):
            return False
        
        n=len(s1)
        m=len(s2)
        
        dp=[]
        row=[0]*(n+1)
        
        for i in range(m+1):
            dp.append(row[:])
            
        dp[0][0]=1
        
        for j in range(m+1):
            for k in range(n+1):
                if j==0 and k==0:
                    continue
                if j==0 and dp[j][k-1]==1 and s3[j+k-1]==s1[k-1]:
                    dp[j][k]=1
                elif k==0 and dp[j-1][k]==1 and s3[j+k-1]==s2[j-1]:
                    dp[j][k]=1
                elif dp[j-1][k]==1 and s3[j+k-1]==s2[j-1] or dp[j][k-1]==1 and s3[j+k-1]==s1[k-1]:
                    dp[j][k]=1
        
        return dp[m][n]==1