当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.097.Interleaving String 交错字符串

LeetCode.097.Interleaving String 交错字符串

题目描述

97 Interleaving String
https://leetcode-cn.com/problems/interleaving-string/

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

解题过程

为什么双指针法是错的

双指针法这样操作:i 指向 s1, j 指向 s2, k 指向 s3 每次比较 s3[k] 和 s1[i], s2[j] 中的哪个相等,相等的两个指针都右移一位。
双指针法的问题是,当 s1[i] 和 s2[j] 都和 s3[k] 相等时,我们默认选择 s1[i] 进行匹配,但这个当前的选择可能导致之后的匹配无法完成,因为这个位置可能使用 s2[j] 去匹配才是正确的,但我们又没有回溯过程,就会导致判断错误。

回溯法

双指针法的问题通过回溯可以解决,遇到 s1[i] 和 s2[j] 都和 s3[k] 相同时,先走到 s1[i] 和 s3[k] 匹配的分支,如果成功则不需要再看 s2[j],否则回溯再看 s2[j] 和 s3[k] 匹配的分支,从这个描述中也能看出通过 DFS 递归实现很方便。

动态规划

dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符能否构成 s3 前 i+j 个字符
dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]) || (s2[j-1] == s3[i+j-1] && dp[i][j-1])
即 如果 s1 第 i 个字符和 s3 第 i+j 个字符相等,则 dp[i][j] 的结果取决于 dp[i-1][j] ,或者 如果 s2 第 j 个字符和 s3 第 i+j 个字符相等,则 dp[i][j] 的结果取决于 dp[i][j-1],这两个情况只有满足其一则 dp[i][j] 就是 true
初始条件 dp[0][0] = true

时间复杂度 O(mn),空间复杂度 O(mn)

由于 dp[i][j] 只依赖 dp[i-1][j]dp[i][j-1],所以没必要构建整个 dp 二维数组,使用滚动数组的思想,只需要保存 dp 数组的 第 i-1 行即可。下面的代码中没使用滚动数组。

private static class SolutionV202007 {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        // dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符能否构成 s3 前 i+j 个字符
        // 则 dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]) || (s2[j-1] == s3[i+j-1] && dp[i][j-1])
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];

        // 遍历填表,i,j 遍历的是 dp 二维数组
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                    continue;
                }
                if (i - 1 >= 0) {
                    dp[i][j] = s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j];
                    if (dp[i][j]) {
                        continue;
                    }
                }
                if (j - 1 >= 0) {
                    dp[i][j] = s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1];
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}

GitHub代码

algorithms/leetcode/leetcode/_097_InterleavingString.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_097_InterleavingString.java


上一篇 LeetCode.312.Burst Balloons 戳气球

下一篇 Spring-Data-JPA

阅读
评论
775
阅读预计3分钟
创建日期 2020-07-18
修改日期 2020-07-18
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论