Last updated on March 7th, 2025 at 08:41 pm
Here, we see an Interleaving String LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, String
Level of Question
Medium
Interleaving String LeetCode Solution
Table of Contents
1. 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.
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Dynamic Programming”. This pattern is used to solve problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results for future use. Specifically, this problem is a variation of the “0/1 Knapsack” pattern, where we decide whether to include characters from s1 or s2 to match s3.
3. Code Implementation in Different Languages
3.1 Interleaving String 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];
}
};
3.2 Interleaving String 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.3 Interleaving String 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();
};
3.4 Interleaving String 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n1 * n2) | O(n1 * n2) |
| Java | O(2(n1 + n2)) | O(n1 * n2) |
| JavaScript | O(2(n1 + n2)) | O(n1 * n2) |
| Python | O(n1 * n2) | O(n1 * n2) |
- C++ and Python use an iterative DP approach with O(n1 * n2) time and space complexity.
- Java and JavaScript use a recursive DFS approach with memoization, leading to exponential time complexity (O(2^(n1 + n2))) but optimized with O(n1 * n2) space complexity.