97. 交错字符串
97. 交错字符串
题目
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 + ... + sn
t = 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 <= 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?
题目大意
给定三个字符串 s1
、s2
、s3
,请判断 s3
能不能由 s1
和 s2
交织(交错) 组成。
两个字符串 s
和 t
交织 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串:
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
- 交织 是
s1 + t1 + s2 + t2 + s3 + t3 + ...
或者t1 + s1 + t2 + s2 + t3 + s3 + ...
提示:
a + b
意味着字符串a
和b
连接。0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1
、s2
、和s3
都由小写英文字母组成
进阶: 您能否仅使用 O(s2.length)
额外的内存空间来解决它?
解题思路
思路一:动态规划
动态规划:
- 使用一个二维布尔数组
dp
,其中dp[i][j]
表示s3
的前i + j
个字符可以由s1
的前i
个字符和s2
的前j
个字符交错形成。
- 使用一个二维布尔数组
状态转移:
- 初始化
dp[0][0]
为true
,表示空字符串可以由两个空字符串交错形成。 - 然后填充
dp
表:- 如果
s1[i-1]
和s3[i+j-1]
相等,则dp[i][j]
可以从dp[i-1][j]
转移而来。 - 如果
s2[j-1]
和s3[i+j-1]
相等,则dp[i][j]
可以从dp[i][j-1]
转移而来。
- 如果
- 初始化
最终结果:
dp[s1.length][s2.length]
表示s3
是否可以由s1
和s2
交错形成。
复杂度分析
- 时间复杂度:
O(m * n)
,需要填充整个dp
数组。 - 空间复杂度:
O(m * n)
,使用的 DP 数组。
思路二:动态规划+压缩状态
要通过使用一维数组代替二维数组,可以将思路一的空间复杂度优化到 O(n)
。
- 我们只需要保留当前行的信息,因此可以用一个长度为
n + 1
的一维数组来存储状态。 - 创建一个长度为
n + 1
的一维数组dp
,并初始化dp[0]
为true
。 - 处理
s2
的字符,初始化dp
的第一行。 - 处理
s1
的字符,更新dp
数组。 - 在更新时,从后向前更新,以防止覆盖之前的数据。使用当前
dp[j]
和dp[j - 1]
来判断是否可以交错形成s3
的相应部分。
复杂度分析
- 时间复杂度:
O(m * n)
,与之前相同。 - 空间复杂度:
O(n)
,通过使用一维数组代替二维数组来减少空间使用。
总结:
代码
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function (s1, s2, s3) {
const m = s1.length,
n = s2.length;
if (m + n !== s3.length) return false;
let dp = new Array(m + 1).fill(0).map((i) => new Array(n + 1).fill(false));
dp[0][0] = true;
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i > 0 && s1[i - 1] == s3[i - 1 + j]) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
if (j > 0 && s2[j - 1] == s3[i + j - 1]) {
dp[i][j] = dp[i][j] || dp[i][j - 1];
}
}
}
return dp[m][n];
};
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function (s1, s2, s3) {
const m = s1.length,
n = s2.length;
if (m + n !== s3.length) return false;
let dp = new Array(n + 1);
dp[0] = true;
for (let j = 0; j <= n; j++) {
dp[j] = j === 0 || (dp[j - 1] && s2[j - 1] === s3[j - 1]);
}
for (let i = 1; i <= m; i++) {
dp[0] = dp[0] && s1[i - 1] === s3[i - 1];
for (let j = 1; j <= n; j++) {
dp[j] =
(dp[j] && s1[i - 1] === s3[i + j - 1]) ||
(dp[j - 1] && s2[j - 1] === s3[i + j - 1]);
}
}
return dp[n];
};