交错字符串
难度:
标签:
题目描述
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- 交错 是
s1 + t1 + s2 + t2 + s3 + t3 + ...或者t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。
示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出：true
示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出：false
示例 3：
输入：s1 = "", s2 = "", s3 = "" 输出：true
提示：
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1、s2、和s3都由小写英文字母组成
进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?
代码结果
运行时间: 23 ms, 内存: 16.2 MB
// 思路：
// 使用流的特性解决问题，但由于流的操作特性，直接使用流来解决动态规划问题不太适合。
// 因此，这里使用类似的动态规划思路，但用流来简化部分操作。
import java.util.stream.IntStream;
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length();
int n = s2.length();
if (m + n != s3.length()) return false;
boolean[] dp = new boolean[n + 1];
dp[0] = true;
IntStream.range(1, n + 1).forEach(j -> dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1));
for (int i = 1; i <= m; i++) {
dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
IntStream.range(1, n + 1).forEach(j -> dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
|| (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)));
}
return dp[n];
}解释
方法:
这个题解使用动态规划的思路来解决交错字符串的问题。定义状态 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i+j 个字符。状态转移方程为：如果 dp[i][j-1] 为 true 且 s2[j-1] 等于 s3[i+j-1]，或者 dp[i-1][j] 为 true 且 s1[i-1] 等于 s3[i+j-1]，那么 dp[i][j] 为 true。最终结果为 dp[n][m]，其中 n 和 m 分别为 s1 和 s2 的长度。
时间复杂度:
O(nm)
空间复杂度:
O(nm)
代码细节讲解
🦆
请问在动态规划数组dp中，dp[i][j]为true是什么意思？
▷🦆
为什么在初始化时，只有当s1的第i-1个字符等于s3的第i-1个字符时，dp[i][0]才设置为true？
▷🦆
在边界条件中，你设置了当s2为空时，只考虑s1和s3的匹配情况。如果s1也为空，dp[0][0]的值应该是什么？
▷🦆
状态转移方程中使用了`dp[i][j-1]`和`s2[j-1] == s3[i+j-1]`，这种方式是否考虑了所有可能的字符匹配组合？
▷