LeetCode97-交错字符串

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/interleaving-string/

中文链接：https://leetcode-cn.com/problems/interleaving-string/

题目详述

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

示例 1:

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

示例 2:

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

题目详解

  • 字符串的动态规划问题，比较经典的有 LeetCode72-编辑距离。
  • f(i, j) 表示 s1 的前 i 个字符和 s2 的前 j 个字符是否可以交错组成 s3 的前 i + j 个字符。
  • 状态转移：如果 s1[i] == s3[i + j]，则问题转化为了 f[i - 1][j]；如果 s2[j] == s3[i + j]，则问题转化为了 f[i][j - 1]。两种情况只要有一种为真，则 f[i][j] 就为真。
  • 注意初始化。
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
27
28
29
30
public class LeetCode_00097 {

    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        int k = s3.length();
        if (m + n != k) {
            return false;
        }
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 1; i <= m; ++i) {
            f[i][0] = f[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }
        for (int i = 1; i <= n; ++i) {
            f[0][i] = f[0][i - 1] && s2.charAt(i - 1) == s3.charAt(i - 1);
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
                    f[i][j] |= f[i - 1][j];
                }
                if (s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
                    f[i][j] |= f[i][j - 1];
                }
            }
        }
        return f[m][n];
    }
}