一、题目
1、算法题目
“给定三个字符串s1、s2、s3，验证s3是否是s1和s2的交错组成的。”
题目链接：
来源：力扣（LeetCode）
链接：97. 交错字符串 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定三个字符串 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： 输入： s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出： true 复制代码
示例 2： 输入： s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出： false 复制代码
二、解题
1、思路分析
这道题比较容易想到的是用双指针来解题，指针p1指向字符串s1的头部，另一个指针p2指向字符串s2的头部，指针p3指向s3的头部，这样每次判断指针p1和p2指向的元素是否相同，相同则向后移动指针。
但是这种方法会出现错误，比如s1="aabcc"，s2="dbbca"，s3="aabbbcbcac"时，得到的结果是false，实际应该是true。
重新分析题意，如果s1+s2≠s3，那么s3必然不可能是s1和s2的交错，如果s1+s2=s3的时候就可以使用动态规划来求解：
- 如果s1的前i个字符与s2的前j个字符拼接成s3的i+j字符，也就是存在目标路径能够到达i，j
- 如果f(i-1,j)为真，则f(i,j)为真
- 如果f(i,j-1)为真，则f(i,j)为真
- 其他情况为false
2、代码实现
代码参考：
class Solution { public boolean isInterleave(String s1, String s2, String s3) { int n = s1.length(), m = s2.length(), t = s3.length(); if (n + m != t) { return false; } boolean[] f = new boolean[m + 1]; f[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[j] = f[j] && s1.charAt(i - 1) == s3.charAt(p); } if (j > 0) { f[j] = f[j] || (f[j - 1] && s2.charAt(j - 1) == s3.charAt(p)); } } } return f[m]; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(nm)
两重循环的时间代价为o(nm)。
空间复杂度： O(m)
空间复杂度为s2的长度。
三、总结
这道题使用了动态规划解题，之后又用了滚动数组优化这个动态规划。
对于动态规划解题的相似题目还有：
- 63.不同路径 Ⅱ
- 70.爬楼梯
