Leetcode(97) Interleaving String

发表于 | 分类于

Description

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

Example 1:

1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

解法

首先明确，这种题用递归解肯定是超时的，那么采用动态规划优化时间，这里对于s3字符串的匹配可能出现两种情况，一种是采用s1中的字符与其匹配，一种是采用s2中的字符与之匹配。设计二维dp表格。

s1, s2只有两个字符串，因此可以展平为一个二维地图，判断是否能从左上角走到右下角。

当s1到达第i个元素，s2到达第j个元素:

地图上往右一步就是s2[j-1]匹配s3[i+j-1]。

地图上往下一步就是s1[i-1]匹配s3[i+j-1]。

示例：s1=”aa”,s2=”ab”,s3=”aaba”。标1的为可行。最终返回右下角。

​ 0 a b

0 1 1 0

a 1 1 1

a 1 0 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
34
35
36
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        if (s1.length() == 0 && s2.length() == 0) {
            if (s3.length() == 0) {
                return true;
            }
            return false;
        }
        Boolean[][] dp = new Boolean[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i < s1.length() + 1; i++) {
            for (int j = 0; j < s2.length() + 1; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (j == 0) {
                    if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
                        dp[i][0] = dp[i - 1][0];
                    } else {
                        dp[i][0] = false;
                    }
                } else if (i == 0) {
                    if (s2.charAt(j - 1) == s3.charAt(j - 1)) {
                        dp[0][j] = dp[0][j - 1];
                    } else {
                        dp[0][j] = false;
                    }
                } else {
                    dp[i][j] = (dp[i - 1][j] && (s1.charAt(i - 1) == s3.charAt(i + j - 1))) || (dp[i][j - 1] && (s2.charAt(j - 1) == s3.charAt(j + i - 1)));
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}