97.交错字符串
97. 交错字符串
题意
给定三个字符串 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 连接。
难度
中等
示例
示例 1：
097.%E4%BA%A4%E9%94%99%E5%AD%97%E7%AC%A6%E4%B8%B2-
20231106163826.png
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true
示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true
分析
可能有些小伙伴一看到字符串的问题，很容易想到暴力枚举的方法，但很不幸，这道题不
适合，因为题目的附加条件中明确指出，s1、s2 字符串的最大长度为 100，暴力枚举的
时间开销难以承受。
换个角度，既然 0 <= s1.length, s2.length <= 100，那我们不妨利用动态规划来解题。
第一步，确定状态，我们假设 f[i][j]为使用了 i 个 s1 的字符，和 j 个 s2 的字符来匹配 s3
的前 i+j 个字符。
那么最初的状态肯定是 f[0][0] = true
因为空串和空串是匹配的，示例 3 也给出来了。
第二步，确定动态转移方程，第一步已经确定了前面的 i + j - 1 个字符，接下来如果要确
定 f[i][j]的字符，无非是从 f[i-1][j]和 f[i][j-1]两种状态转移，如果能够转移，则需要这二
者其中之一为真。
如果是从 f[i-1][j]转移来的话，s1.charAt(i)肯定要与 s3.charAt(i+j)相等，如果是从 f[i]
[j-1]转移来的话，s2.charAt(j)肯定要与 s3.charAt(i+j)相等。
为什么？
因为我们的 f[i][j]是用 i 个 s1 的字符和 j 个 s2 的字符来匹配 s3 的前 i+j 个字符，那么我们
的 f[i][j]的最后一个字符肯定是 s1.charAt(i)或者 s2.charAt(j)，所以我们的动态转移方程
就出来了：
$
$
考虑到字符串存储的实际情况，我们的题解需要稍作改动。
int pos = i + j - 1;
if (i > 0) {
f[i][j] = f[i][j] || (f[i - 1][j] && (s1.charAt(i - 1) == s3.charAt(pos)));
}
if (j > 0) {
f[i][j] = f[i][j] || (f[i][j - 1] && (s2.charAt(j - 1) == s3.charAt(pos)));
}
注意，字符串是以 0 位置开始计数的。
答案一目了然：因为题目要求的是整个字符串的匹配，所以 s1 和 s2 都必须全都用完，那
么答案自然存储在 f[s1.length()][s2.length()]。
class Solution {
// 定义 isInterleave 方法
public boolean isInterleave(String s1, String s2, String s3) {
// 获取 s1 和 s2 的长度
int n = s1.length(), m = s2.length();
// 如果 s1 和 s2 长度之和不等于 s3 的长度，直接返回 false
if (n + m != s3.length()) {
return false;
}
// 创建一个二维数组 f 来保存中间结果，f[i][j]表示 s1 的前 i 个字符和 s2 的前 j 个字符是否
能交错组成 s3 的前 i+j 个字符
boolean[][] f = new boolean[n + 1][m + 1];
// 初始化 f[0][0]为 true，表示空字符串是可以交错组成的
f[0][0] = true;
// 遍历 s1 和 s2 的所有字符组合
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// pos 用于定位当前在 s3 中的位置
int pos = i + j - 1;
// 如果 i 大于 0，我们需要检查 s1 的第 i 个字符和 s3 的第 pos 个字符是否匹配
if (i > 0) {
f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(pos));
}
// 如果 j 大于 0，我们需要检查 s2 的第 j 个字符和 s3 的第 pos 个字符是否匹配
if (j > 0) {
f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(pos));
}
}
}
// 最终返回 f[n][m]，它表示 s1 和 s2 是否能交错组成 s3
return f[n][m];
}
}
假如输入是 s1 = “aabcc”, s2 = “dbbca”, 和 s3 = “aadbbcbcac”，我们来模拟一下整个题解的
过程：
1. 当 i 和 j 都为 0 时，f[0][0] 为 true。
2. 当 i = 1 时，我们检查 s1[0] 是否等于 s3[0]，发现 'a' == 'a'，所以 f[1][0] 为 true。
3. 当 i = 2 时，我们继续检查 s1[0...1] 是否可以形成 s3[0...1]，发现 'aa' == 'aa'，所
以 f[2][0] 为 true。
4. 对于 j = 1，我们检查 s2[0] 是否等于 s3[0]，因为 'd' != 'a'，f[0][1] 保持 false。
5. 对于 i = 1 和 j = 1，我们需要检查 s1[0] 和 s2[0] 是否可以交错形成 s3[0...1]。因为
f[1][0] 是 true 并且 'a' == 'a'，同时 f[0][1] 是 false，所以 f[1][1] 变成 true。
继续，对于 i = 2, j = 1，s1[0...1] 和 s2[0] 是否可以交错形成 s3[0...2]。以此类推，我
们继续检查所有可能的 i 和 j 的组合。
最终，我们填充完整个 f 数组。如果 f[s1.length()][s2.length()] 为 true，则表示 s1 和 s2
可以交错形成 s3。
来看一下题解效率：
097.%E4%BA%A4%E9%94%99%E5%AD%97%E7%AC%A6%E4%B8%B2-
20231106170113.png
我们把题解改造为 ACM 输入输出模式，然后 debug 看一下：
import java.util.Scanner;
public class InterleavingString {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入
String s1 = scanner.nextLine();
String s2 = scanner.nextLine();
String s3 = scanner.nextLine();
// 调用函数并输出结果
System.out.println(isInterleave(s1, s2, s3));
}
public static boolean isInterleave(String s1, String s2, String s3) {
int n = s1.length(), m = s2.length();
if (n + m != s3.length()) {
return false;
}
boolean[][] f = new boolean[n + 1][m + 1];
f[0][0] = true;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
int p = i + j - 1;
if (i > 0) {
f[i][j] |= (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
}
if (j > 0) {
f[i][j] |= (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
}
}
}
return f[n][m];
}
}
可以 debug 看一下输入输出
097.%E4%BA%A4%E9%94%99%E5%AD%97%E7%AC%A6%E4%B8%B2-
20231106171013.png
总结
一不小心，我们又解决了一道动态规划的难题！随着练习，我们可以发现，动态规划并非
什么恐怖的怪兽，它有着独特的解题过程和方法，是可以被攻克的，只要我们不断练习，
最终都会将其拿下。
力扣链接：https://leetcode.cn/problems/interleaving-string/