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

恬静的小魔龙

发布于 2022-08-07 10:22:37

2200

发布于 2022-08-07 10:22:37

文章被收录于专栏：Unity3DUnity3D

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

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] &amp;&amp; s1.charAt(i - 1) == s3.charAt(p);
                }
                if (j > 0) {
                    f[j] = f[j] || (f[j - 1] &amp;&amp; s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }

        return f[m];
    }
}

3、时间复杂度

时间复杂度： O(nm)

两重循环的时间代价为o(nm)。

空间复杂度： O(m)

空间复杂度为s2的长度。

三、总结

这道题使用了动态规划解题，之后又用了滚动数组优化这个动态规划。

对于动态规划解题的相似题目还有：

63.不同路径 Ⅱ
70.爬楼梯

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-02-09，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度