Last updated on October 10th, 2024 at 12:30 am
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
Topics
Dynamic Programming, String
Level of Question
Medium
Interleaving String LeetCode Solution
Table of Contents
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 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- The interleaving is
s1 + t1 + s2 + t2 + s3 + t3 + ...ort1 + s1 + t2 + s2 + t3 + s3 + ...
Note: a + b is the concatenation of strings a and b.
1. 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];
}
};2. 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;
}
}3. 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();
};4. 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