# Interleaving String LeetCode Solution

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

## 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``````
Scroll to Top