Dare2Solve
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.
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]
.
Initial Check:
s1
and s2
is not equal to the length of s3
, return false
since it's not possible for s3
to be an interleaving.DP Array Initialization:
dp
of size (m+1) x (n+1)
, where m
is the length of s1
and n
is the length of s2
. Initialize all values to False
.Base Case:
dp[m][n]
to True
because an empty s1
and s2
interleave to form an empty s3
.Fill the DP Table:
s1
and s2
to the beginning.(i, j)
, check the following:
s1[i]
matches s3[i + j]
and the substring starting at s1[i+1]
and s2[j]
can interleave to form the substring starting at s3[i+j+1]
, set dp[i][j]
to True
.s2[j]
matches s3[i + j]
and the substring starting at s1[i]
and s2[j+1]
can interleave to form the substring starting at s3[i+j+1]
, set dp[i][j]
to True
.Return the Result:
dp[0][0]
, indicating whether s1
and s2
can interleave to form s3
. Return this value.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)
.
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.
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<vector<bool>> dp(m + 1, vector<bool>(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];
}
};
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]
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];
}
}
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]
};