97. 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.

解法1： DP O(len_s1 * len_s2) Time and space

拿到题目似乎就是用dp来做，其他没有比较好的办法可以套。
那么就从小问题开始。
如果一个string是空，那么s3必须和另一个string相等。
如果用dp[i][j] 表示的是前i个字符和前j个字符组成的string可以是前(i+j)的interleave，那么就可以知道
i+j上的字符一定要么等于s1的第i个字符或者是s2的第j个字符。同时，如果这个条件满足，则就考虑
dp[i -1][j]或者dp[i][j - 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
27
28
29
30
31
32
33
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (s3.length() != s1.length() + s2.length()) return false;
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        for (int col = 1; col <= len2; col++) {
            dp[0][col] = s2.substring(0, col).equals(s3.substring(0, col));
        }
        for (int row = 1; row <= len1; row++) {
            dp[row][0] = s1.substring(0, row).equals(s3.substring(0,row));
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                int len = i + j;
                if (s3.charAt(len - 1) == s1.charAt(i - 1) && dp[i - 1][j]) {
                    dp[i][j] = true;
                }
                if (s3.charAt(len - 1) == s2.charAt(j - 1) && dp[i][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[len1][len2];
    }
}