97\. Interleaving String
# 97. Interleaving String (opens new window)
# Description
Difficulty: Medium
Related Topics: String (opens new window), Dynamic Programming (opens new window)
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
non-empty substrings respectively, such that:
- s = s1 + s2 + ... + sn
- t = t1 + t2 + ... + tm
|n - m| <= 1
- The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + 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.
1
2
3
4
5
6
2
3
4
5
6
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.
1
2
3
2
3
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
1
2
2
Constraints:
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1
,s2
, ands3
consist of lowercase English letters.
Follow up: Could you solve it using only O(s2.length)
additional memory space?
# Solution
Language: JavaScript
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
const [n, m] = [s1.length + 2, s2.length + 2];
if (m + n - 4 !== s3.length) return false;
const dp = new Uint8Array(m);
dp[1] = 1;
for (let i = 1; i < n; i++) {
for (let j = 1; j < m; j++) {
const up = dp[j] && s1[i - 2] === s3[i + j - 3];
const left = dp[j - 1] && s2[j - 2] === s3[i + j - 3]
dp[j] = up || left;
}
}
return dp[m - 1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23