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

---