Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
GeeksforGeeks
ProgramCreek
YouTube
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Last updated
Was this helpful?
Was this helpful?
/**
* Time complexity : O(2^(m+n)). m is the length of s1 and n is the length of s2.
* Space complexity : O(m+n). The size of stack for recursive calls
* can go upto m+n.
*/
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if(m+n != s3.length()) return false;
return helper(s1, m, 0, s2, n, 0, s3, "");
}
private boolean helper(String s1, int m, int i,
String s2, int n, int j,
String s3,
String s) {
if(s3.equals(s) && i == m && j == n) {
return true;
}
boolean ans = false;
if(i < m) {
ans |= helper(s1, m, i+1, s2, n, j, s3, s+s1.charAt(i));
}
if(j < n) {
ans |= helper(s1, m, i, s2, n, j+1, s3, s+s2.charAt(j));
}
return ans;
}
}/**
* Time complexity : O(m*n). dp array of size m*n is filled.
* Space complexity : O(m*n). 2D dp of size (m+1)*(n+1) is required. m and n are
* the lengths of strings s1 and s2 respectively.
*/
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length(), p = s3.length();
if(m+n != p) return false;
char[] s1Chars = s1.toCharArray();
char[] s2Chars = s2.toCharArray();
char[] s3Chars = s3.toCharArray();
boolean[][] dp = new boolean[m+1][n+1];
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(i == 0 && j == 0) {
dp[i][j] = true;
} else if(i == 0) {
dp[i][j] = dp[i][j-1] && s2Chars[j-1] == s3Chars[i+j-1];
} else if(j == 0) {
dp[i][j] = dp[i-1][j] && s1Chars[i-1] == s3Chars[i+j-1];
} else {
dp[i][j] = (dp[i-1][j] && s1Chars[i-1] == s3Chars[i+j-1]) ||
(dp[i][j-1] && s2Chars[j-1] == s3Chars[i+j-1]);
}
}
}
return dp[m][n];
}
}/**
* Time complexity : O(m*n). dp array of size n is filled m times.
* Space complexity : O(n). n is the length of the string s1.
*/
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if(m+n != s3.length()) return false;
boolean[] dp = new boolean[n+1];
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(i == 0 && j == 0) {
dp[j] = true;
} else if(i == 0) {
dp[j] = dp[j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
} else if(j == 0) {
dp[j] = dp[j] && s1.charAt(i-1) == s3.charAt(i+j-1);
} else {
dp[j] = (dp[j] && s1.charAt(i-1) == s3.charAt(i+j-1)) ||
(dp[j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
}
}
}
return dp[n];
}
}