# 97. Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
# Solution
Approach 1: DP.
Approach 2: DP with less space.
Approach 3: Recursion + memorization.
# Code (Python)
Approach 1:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
# match[i][j]: if the first i letters of s1 and first j letters of s2 interleaves the first i+j letters of s3
match = [[False for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
for i in range(len(match)):
for j in range(len(match[0])):
if i == 0 and j == 0:
match[i][j] = True
continue
if i == 0:
match[i][j] = (s3[i+j-1] == s2[j-1] and match[i][j-1])
continue
if j == 0:
match[i][j] = (s3[i+j-1] == s1[i-1] and match[i-1][j])
continue
if i > 0 and s3[i+j-1] == s1[i-1]:
match[i][j] = match[i][j] or match[i-1][j]
if j > 0 and s3[i+j-1] == s2[j-1]:
match[i][j] = match[i][j] or match[i][j-1]
return match[-1][-1]
# space can be optimized to linear
# Code (C++)
Approach 1:
// DP
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1 = s1.size();
int n2 = s2.size();
int n3 = s3.size();
if (n1 + n2 != n3)
return false;
if (n1 == 0)
return s2 == s3;
if (n2 == 0)
return s1 == s3;
bool match[n1+1][n2+1];
match[0][0] = true;
for (int i = 0; i <= n1; ++i)
{
for (int j = 0; j <= n2; ++j)
{
if (i + j > 0)
{
match[i][j] =
(i > 0 && s1[i-1] == s3[i+j-1] && match[i-1][j]) ||
(j > 0 && s2[j-1] == s3[i+j-1] && match[i][j-1]);
}
}
}
return match[n1][n2];
}
};
Approach 2:
// DP with less space.
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1 = s1.size();
int n2 = s2.size();
int n3 = s3.size();
if (n1 + n2 != n3)
return false;
if (n1 == 0)
return s2 == s3;
if (n2 == 0)
return s1 == s3;
bool match[n2+1];
match[0] = true;
for (int i = 0; i <= n1; ++i)
{
for (int j = 0; j <= n2; ++j)
{
if (i + j > 0)
{
match[j] =
(i > 0 && s1[i-1] == s3[i+j-1] && match[j]) ||
(j > 0 && s2[j-1] == s3[i+j-1] && match[j-1]);
}
}
}
return match[n2];
}
};
Approach 3:
// Recursion + memorization.
class Solution {
private:
unordered_map<string,bool> umap;
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1 > s2)
std::swap(s1, s2);
int n1 = s1.size();
int n2 = s2.size();
int n3 = s3.size();
if (n1 + n2 != n3)
return false;
if (n1 == 0)
return s2 == s3;
if (n2 == 0)
return s1 == s3;
string key = s1 + "," + s2 + "," + s3;
if (umap.find(key) != umap.end())
return umap[key];
bool match = false;
if (s1[n1-1] == s3[n3-1] && isInterleave(s1.substr(0, n1-1), s2, s3.substr(0, n3-1)))
match = true;
else if (s2[n2-1] == s3[n3-1] && isInterleave(s1, s2.substr(0, n2-1), s3.substr(0, n3-1)))
match = true;
umap[key] = match;
return match;
}
};