Interleaving String Problem: Given strings s1
, s2
, and s3
, find whether s3
is formed by an interleaving of s1
and s2
.
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true
Table of Contents
Interleaving String Problem Solution
Problem Solution In Python
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
found = False
memo = set()
def interleave(i,j):
nonlocal memo, s1, s2, s3, found
if (i,j) in memo:
return
if found: return
if i == len(s1)-1 and j == len(s2)-1:
found = True
k = i+j+2
memo.add((i,j))
if i+1 < len(s1) and s1[i+1] == s3[k]:
interleave(i+1, j)
if j+1 < len(s2) and s2[j+1] == s3[k]:
interleave(i,j+1)
interleave(-1,-1)
return found
Problem Solution In Java
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length()+s2.length() != s3.length()) return false;
char[] a1 = s1.toCharArray();
char[] a2 = s2.toCharArray();
char[] a3 = s3.toCharArray();
int[][] dp = new int[a1.length+1][a2.length+1];
return helper(a1, a2,a3,0,0,0,dp);
}
boolean helper(char[] a1, char[] a2, char[] a3, int i1, int i2, int i3, int[][] dp) {
if(i1==a1.length && i2==a2.length && i3==a3.length) return true;
if(dp[i1][i2]!=0) return false;
if(i1<a1.length && a1[i1]==a3[i3] ) {
if(helper(a1, a2, a3, i1+1, i2, i3+1,dp)) return true;
}
if(i2<a2.length && a2[i2]==a3[i3]){
if(helper(a1, a2, a3, i1, i2+1, i3+1, dp)) return true;
}
dp[i1][i2]=1;
return false;
}
}
Problem Solution In C++
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int M, N;
M = s1.length();
N = s2.length();
if (s3.length() != M + N)
return false;
bool T[M+1][N+1];
T[0][0] = true;
for (int j = 1; j <= N; ++j)
T[0][j] = T[0][j-1] && s2[j-1] == s3[j-1];
for (int i = 1; i <= M; ++i)
T[i][0] = T[i-1][0] && s1[i-1] == s3[i-1];
for (int i = 1; i <= M; ++i)
for (int j = 1; j <= N; ++j)
T[i][j] = (T[i-1][j] && s1[i-1] == s3[i+j-1] ) || (T[i][j-1] && s2[j-1] == s3[i+j-1] );
return T[M][N];
}
};
Problem Solution In C
bool dp[1010];
bool isInterleave(char* s1, char* s2, char* s3) {
int aLen = strlen(s1), bLen = strlen(s2), cLen = strlen(s3);
if(aLen + bLen != cLen) return false;
dp[0] = true;
for(int j = 1; j <= bLen; j++)
dp[j] = dp[j - 1] && (s2[j - 1] == s3[j - 1]);
for(int i = 1; i <= aLen; i++){
char cur = s1[i - 1];
dp[0] = dp[0] && (s1[i - 1] == s3[i - 1]);
for(int j = 1; j <= bLen; j++)
dp[j] = (dp[j] && cur == s3[i + j - 1]) || (dp[j - 1] && s2[j - 1] == s3[i + j - 1]);
}
return dp[bLen];
}