☆打卡算法☆LeetCode 97、交错字符串 算法解析

一、题目

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.爬楼梯