交错字符串

发表于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，97. Interleaving String

先看题目描述

大意就是给定三个字符串 s1, s2, s3，判断 s3 是否由 s1 和 s2 交错组成

算法和思路

第一反应是双指针，但尝试实现以后发现不行，看了题解才意识到这题用双指针就踩坑了，应该用动态规划

动态规划

  • dp[i][j] 表示 s1 的前 i 个元素和 s2 的前 j 个元素能否交替组成 s3 的前 i + j 个元素，初始化 dp[0][0] = 0
  • 状态转移方程：dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[p] || dp[i][j - 1] && s2[j - 1] == s3[p]，其中 p = i +j -1
  • 最终返回 dp[s1.length()][s2.length()] 即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) return false;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                int p = i + j - 1;
                if (i > 0) {
                    dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p);
                }
                if (j > 0) {
                    dp[i][j] = dp[i][j] || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p);
                }
            }
        }
        return dp[m][n];
    }
}

使用滚动数组优化空间复杂度，因为这道题的 dp 数组里第 i 行只与第 i - 1 行有关，所以可以用动态数组优化空间，实现源码如下，类似的用动态数组优化空间的题可以看 三角形最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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];
    }
}