友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
97. 交错字符串
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
-
s = s1 + s2 + … + s+n -
t = t1 + t2 + … + t+m -
|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 <= 100 -
0 <= s3.length <= 200 -
s1、s2、和s3都由小写英文字母组成
进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?
思路分析
类似 62. 不同路径，62 题统计有多少种走法。这道题检查“此路是否通”。
dp[r][c] 代表 s1 前 r 个字符与 s2 前 c 个字符拼接成 s3 的 r+c 字符。
\[dp[r][c] = (dp[r-1][c] & s1[r-1] = s3[r+c-1]) | (dp[r][c-1] & s2[c-1] = s3[r+c-1])\]
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-23 18:05:41
*/
public boolean isInterleave(String s1, String s2, String s3) {
int l = s1.length(), m = s2.length(), n = s3.length();
if (l + m != n) {
return false;
}
boolean[][] dp = new boolean[l + 1][m + 1];
dp[0][0] = true;
for (int r = 1; r <= l; r++) {
dp[r][0] = s1.charAt(r - 1) == s3.charAt(r - 1);
if (!dp[r][0]) {
break;
}
}
for (int c = 1; c <= m; c++) {
dp[0][c] = s2.charAt(c - 1) == s3.charAt(c - 1);
if (!dp[0][c]) {
break;
}
}
for (int r = 1; r <= l; r++) {
for (int c = 1; c <= m; c++) {
int i = r + c - 1;
dp[r][c] = (dp[r - 1][c] && s1.charAt(r - 1) == s3.charAt(i))
|| (dp[r][c - 1] && s2.charAt(c - 1) == s3.charAt(i));
}
}
return dp[l][m];
}