Interleaving String

发表于   |   分类于 ， ，

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example

Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

描述

判断字符串 s3 是否由 s1 与 s2 交错组成（不一定按固定间隔交错）

分析

用动态规划的思想，以一个二维数组来存储判断信息

假设下标从 1 开始：
f[i][j] 其中 i 代表 s1 字符串中选取的字符数，j 代表 s2 字符串中选取的字符数
f[i][j] 为 true 时，代表 s3 长度为 i + j 时符合题意

判断 f[i][j] 是否为 true 时，要求其满足：

  • s1 取第 i 个字符进行判断，当 s3[i + j] == s1[i] 时，再判断之前的 i - 1 + j 个字符是否符合条件，即 f[i - 1][j] 是否为 true
  • s2 取第 j 个字符进行判断，当 s3[i + j] == s2[j] 时，再判断之前的 i + j - 1 个字符是否符合条件，即 f[i][j - 1] 是否为 true

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {

        if ((s1.length() + s2.length()) != s3.length()) {
            return false;
        }

        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        boolean[][] f = new boolean[s1.length()][s2.length()];
        f[0][0] = true;

        for (int i = 1; i < s1.length(); i++) {
            if (s1.charAt(i) == s3.charAt(i) && f[i - 1][0]) {
                f[i][0] = true;
            }
        }

        for (int j = 1; j < s2.length(); j++) {
            if (s2.charAt(j) == s3.charAt(j) && f[0][j - 1]) {
                f[0][j] = true;
            }
        }

        for (int i = 1; i < s1.length(); i++) {
            for (int j = 1; j < s2.length(); j++) {

                if (s3.charAt(i + j) == s1.charAt(i) && f[i - 1][j]) {
                    f[i][j] = true;
                }

                if (s3.charAt(i + j) == s2.charAt(j) && f[i][j - 1]) {
                    f[i][j] = true;
                }
            }
        }

        return f[s1.length() - 1][s2.length() - 1];
    }
}