1.题目

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：
① s = s₁ + s₂ + … + s_n
② t = t₁ + t₂ + … + t_m
③ |n - m| <= 1
④ 交错 是 s₁ + t₁ + s₂ + t₂ + s₃ + t₃ + … 或者 t₁ + s₁ + t₂ + s₂ + t₃ + s₃ + …
注意：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) 额外的内存空间来解决它?

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/interleaving-string

2.思路

（1）动态规划
思路参考本题官方题解。

① 定义 dp 数组，dp[i][j] = true 表示 s3 前 i + j 个字符由 s1 的前 i 个字符和 s2 的前 j 个字符交错组成，否则则不能。

 boolean[][] dp = new boolean[s1Len + 1][s2Len + 1];
1

② 分析状态，当 dp[i][j] 无非就两种情况：true 或 false。

③ 状态转移方程。显然 dp[i][j] 的结果与 dp[i - 1][j] 和 dp[i][j - 1] 均有关：

1）如果 s1 的第 i 个元素和 s3 的第 i + j 个元素相等，那么 dp[i][j] 就取决于 dp[i - 1][j]；
2）如果 s2 的第 j 个元素和 s3 的第 i + j 个元素相等，那么 dp[i][j] 就取决于 dp[i][j - 1]；
1
2

所以可以推导出状态转移方程如下：

p = i + j - 1;
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p))
1
2

3.代码实现（Java）

//思路1————动态规划
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int s1Len = s1.length();
        int s2Len = s2.length();
        int s3Len = s3.length();
        if (s1Len + s2Len != s3Len) {
            return false;
        }
        //dp[i][j] = true 表示 s3 前 i + j 个字符由 s1 的前 i 个字符和 s2 的前 j 个字符交错组成
        boolean[][] dp = new boolean[s1Len + 1][s2Len + 1];
        //边界条件
        dp[0][0] = true;
        // s1 和 s2 均有可能为空串，所以下标 i 和 j 均从 0 开始
        for (int i = 0; i <= s1Len; i++) {
            for (int j = 0; j <= s2Len; j++) {
                int k = i + j - 1;
                if (i > 0 && s1.charAt(i - 1) == s3.charAt(k)) { 
                    dp[i][j] = dp[i - 1][j];
                }
                if (j > 0 && s2.charAt(j - 1) == s3.charAt(k)) {
                	/*
                		(1) | 与 || 在此处均可以，具体差别就在于后者是短路运算，不过对本题没有影响
						(2) dp[i][j] |= dp[i][j - 1] 就等价于 dp[i][j] = dp[i][j] | dp[i][j - 1]
						(3) 这里之所以要加上 |，其原因在于如果上面的 if 内的条件为 true 且 dp[i][j] 被设置为 true，而下面的 
							dp[i][j - 1] 的结果为 false，在没有 | 的情况下，那么 dp[i][j] 会被错误地赋值为 false，这可能会
							影响最终的结果，所以需要加上 | 来保证 dp[i][j] 不会被错误地赋值。
					*/
                    dp[i][j] |= dp[i][j - 1];
                }
            }
        }
        return dp[s1Len][s2Len];
    }
}

//由于数组 dp 的第 i 行至于第 i - 1 行有关，故可以使用滚动数组优化空间复杂度
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int s1Len = s1.length();
        int s2Len = s2.length();
        int s3Len = s3.length();
        if (s1Len + s2Len != s3Len) {
            return false;
        }
        boolean[] dp = new boolean[s2Len + 1];
        dp[0] = true;
        // s1 和 s2 均有可能为空串，所以下标 i 和 j 均从 0 开始
        for (int i = 0; i <= s1Len; i++) {
            for (int j = 0; j <= s2Len; j++) {
                int k = i + j - 1;
                if (i > 0) {
                    dp[j] &= s1.charAt(i - 1) == s3.charAt(k);
                }
                if (j > 0) {
                    dp[j] |= (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(k));
                }
            }
        }
        return dp[s2Len];
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62