
Description
Given three strings s1
, s2
, and s3
, determine if s3
is formed by an interleaving of s1
and s2
. An interleaving of two strings s1
and s2
is a valid string that contains all the characters of s1
and s2
, and preserves the relative order of characters from both strings.
Intuition
To solve this problem, we can use dynamic programming (DP) to keep track of whether substrings of s3
can be formed by interleaving substrings of s1
and s2
. The idea is to use a 2D DP table where each cell dp[i][j]
represents whether the substring s3[0:i+j]
can be formed by interleaving s1[0:i]
and s2[0:j]
.
Approach
- Initial Check:
- If the combined length of
s1
ands2
is not equal to the length ofs3
, returnfalse
since it's not possible fors3
to be an interleaving. - DP Array Initialization:
- Create a 2D boolean array
dp
of size(m+1) x (n+1)
, wherem
is the length ofs1
andn
is the length ofs2
. Initialize all values toFalse
. - Base Case:
- Set
dp[m][n]
toTrue
because an emptys1
ands2
interleave to form an emptys3
. - Fill the DP Table:
- Iterate over the DP table from the end of
s1
ands2
to the beginning. - For each position(i, j)
, check the following: - If the character ats1[i]
matchess3[i + j]
and the substring starting ats1[i+1]
ands2[j]
can interleave to form the substring starting ats3[i+j+1]
, setdp[i][j]
toTrue
. - If the character ats2[j]
matchess3[i + j]
and the substring starting ats1[i]
ands2[j+1]
can interleave to form the substring starting ats3[i+j+1]
, setdp[i][j]
toTrue
. - Return the Result:
- The result is stored in
dp[0][0]
, indicating whethers1
ands2
can interleave to forms3
. Return this value.
Complexity
Time Complexity:
O(m * n), where m
is the length of s1
and n
is the length of s2
. This is because we need to fill a DP table of size (m+1) x (n+1)
.
Space Complexity:
O(m * n), for storing the DP table. Each cell in the table is used to store whether a substring can be formed by interleaving.
Code
C++
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.length() + s2.length() != s3.length()) return false;
int m = s1.length(), n = s2.length();
vector> dp(m + 1, vector(n + 1, false));
// Base case
dp[m][n] = true;
for (int i = m; i >= 0; --i) {
for (int j = n; j >= 0; --j) {
if (i < m && s1[i] == s3[i + j] && dp[i + 1][j]) {
dp[i][j] = true;
}
if (j < n && s2[j] == s3[i + j] && dp[i][j + 1]) {
dp[i][j] = true;
}
}
}
return dp[0][0];
}
};
Python
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
m, n = len(s1), len(s2)
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Base case
dp[m][n] = True
for i in range(m, -1, -1):
for j in range(n, -1, -1):
if i < m and s1[i] == s3[i + j] and dp[i + 1][j]:
dp[i][j] = True
if j < n and s2[j] == s3[i + j] and dp[i][j + 1]:
dp[i][j] = True
return dp[0][0]
Java
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) return false;
int m = s1.length(), n = s2.length();
boolean[][] dp = new boolean[m + 1][n + 1];
// Base case
dp[m][n] = true;
for (int i = m; i >= 0; --i) {
for (int j = n; j >= 0; --j) {
if (i < m && s1.charAt(i) == s3.charAt(i + j) && dp[i + 1][j]) {
dp[i][j] = true;
}
if (j < n && s2.charAt(j) == s3.charAt(i + j) && dp[i][j + 1]) {
dp[i][j] = true;
}
}
}
return dp[0][0];
}
}
JavaScript
var isInterleave = function(s1, s2, s3) {
if (s1.length + s2.length != s3.length) return false;
var dp = [];
for(let i = 0; i <= s1.length; i++) {
dp.push([]);
for (let j = 0; j <= s2.length; j++) {
dp[i].push(false)
}
}
console.log(dp)
// base case
dp[s1.length][s2.length] = true;
for(let i = s1.length; i >=0; i--) {
for (let j =s2.length; j>=0; j--) {
if (i < s1.length && s1[i] == s3[i+j] && dp[i+1][j]) {
dp[i][j] = true;
}
if (j < s3.length && s2[j] == s3[i+j] && dp[i][j+1]) {
dp[i][j] = true;
}
}
}
return dp[0][0]
};