Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- The interleaving is
s1 + t1 + s2 + t2 + s3 + t3 + ...ort1 + s1 + t2 + s2 + t3 + s3 + ...
Note: a + b is the concatenation of strings a and b.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Explanation: One way to obtain s3 is: Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a". Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac". Since s3 can be obtained by interleaving s1 and s2, we return true.
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.
Example 3:
Input: s1 = "", s2 = "", s3 = "" Output: true
Constraints:
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1,s2, ands3consist of lowercase English letters.
Follow up: Could you solve it using only O(s2.length) additional memory space?
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
@cache
def dfs(i, j):
if i == m and j == n:
return True
return (
i < m
and s1[i] == s3[i + j]
and dfs(i + 1, j)
or j < n
and s2[j] == s3[i + j]
and dfs(i, j + 1)
)
return dfs(0, 0)class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(m + 1):
for j in range(n + 1):
k = i + j - 1
if i:
dp[i][j] = s1[i - 1] == s3[k] and dp[i - 1][j]
if j:
dp[i][j] |= (s2[j - 1] == s3[k] and dp[i][j - 1])
return dp[-1][-1]class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
dp = [False] * (n + 1)
dp[0] = True
for i in range(m + 1):
for j in range(n + 1):
k = i + j - 1
if i:
dp[j] &= (s1[i - 1] == s3[k])
if j:
dp[j] |= (s2[j - 1] == s3[k] and dp[j - 1])
return dp[-1]class Solution {
private int m;
private int n;
private String s1;
private String s2;
private String s3;
private Map<Integer, Boolean> memo = new HashMap<>();
public boolean isInterleave(String s1, String s2, String s3) {
m = s1.length();
n = s2.length();
this.s1 = s1;
this.s2 = s2;
this.s3 = s3;
if (m + n != s3.length()) {
return false;
}
return dfs(0, 0);
}
private boolean dfs(int i, int j) {
System.out.println(i + ", " + j);
if (i == m && j == n) {
return true;
}
if (memo.containsKey(i * 100 + j)) {
return memo.get(i * 100 + j);
}
boolean ret = (i < m && s1.charAt(i) == s3.charAt(i + j) && dfs(i + 1, j)) ||
(j < n && s2.charAt(j) == s3.charAt(i + j) && dfs(i, j + 1));
memo.put(i * 100 + j, ret);
return ret;
}
}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];
dp[0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
int k = i + j - 1;
if (i > 0) {
dp[j] &= (s1.charAt(i - 1) == s3.charAt(k));
}
if (j > 0) {
dp[j] |= (s2.charAt(j - 1) == s3.charAt(k) && dp[j - 1]);
}
}
}
return dp[n];
}
}class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (m + n != s3.size()) return false;
unordered_map<int, bool> memo;
function<bool(int, int)> dfs;
dfs = [&](int i, int j) {
if (i == m && j == n) return true;
auto it = memo.find(i * 100 + j);
if (it != memo.end()) return it->second;
bool ret = (i < m && s1[i] == s3[i + j] && dfs(i + 1, j)) || (j < n && s2[j] == s3[i + j] && dfs(i, j + 1));
memo[i * 100 + j] = ret;
return ret;
};
return dfs(0, 0);
}
};class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (m + n != s3.size()) return false;
vector<int> dp(n + 1);
dp[0] = 1;
for (int i = 0; i <= m; ++i)
{
for (int j = 0; j <= n; ++j)
{
int k = i + j - 1;
if (i) dp[j] &= (s1[i - 1] == s3[k]);
if (j) dp[j] |= (s2[j - 1] == s3[k] && dp[j - 1]);
}
}
return dp[n];
}
};func isInterleave(s1 string, s2 string, s3 string) bool {
m, n := len(s1), len(s2)
if m+n != len(s3) {
return false
}
memo := make(map[int]bool)
var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i == m && j == n {
return true
}
if v, ok := memo[i*100+j]; ok {
return v
}
ret := (i < m && s1[i] == s3[i+j] && dfs(i+1, j)) ||
(j < n && s2[j] == s3[i+j] && dfs(i, j+1))
memo[i*100+j] = ret
return ret
}
return dfs(0, 0)
}func isInterleave(s1 string, s2 string, s3 string) bool {
m, n := len(s1), len(s2)
if m+n != len(s3) {
return false
}
dp := make([]bool, n+1)
dp[0] = true
for i := 0; i <= m; i++ {
for j := 0; j <= n; j++ {
k := i + j - 1
if i > 0 {
dp[j] = dp[j] && (s1[i-1] == s3[k])
}
if j > 0 {
dp[j] = dp[j] || (s2[j-1] == s3[k] && dp[j-1])
}
}
}
return dp[n]
}