leetcode-interleaving-string

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/interleaving-string/

　　给你三个字符串s1,s2,s3，判断s3是否由s1和s2交错形成的，看看下面例子理解一下

1
2
3
4
5
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

题目分析

　　第一种方法是动态规划解决，递推方程可以看代码理解一下，还是比较简单。第二种方法是用记忆化搜索，也比较好理解

代码

　　第一种思路

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
43
44
45
46
47
48
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        if (len1 + len2 != len3) {
            return false;
        } 
        if (len1 == 0) {
            return s2.equals(s3);
        }
        if (len2 == 0) {
            return s1.equals(s3);
        }
        boolean [][] f = new boolean[len1 + 1][len2 + 1];
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        
        // f[0][0]
        f[0][0] = true;
        for (int i = 1; i <= len1; i++) { // s2字符串一个也不拿，只从s1中挑
            if (f[i - 1][0] && c1[i - 1] == c3[i - 1]) {
                f[i][0] = true;
            }    
        }
        for (int j = 1; j <= len2; j++) { // s1字符串一个也不拿，只从s2中挑
            if (f[0][j - 1] && c2[j - 1] == c3[j - 1]) {
                f[0][j] = true;
            }
        }
        // f[i][j]
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (c1[i - 1] == c3[i + j - 1] && f[i - 1][j]) {
                    f[i][j] = true;
                } else if (c2[j - 1] == c3[i + j - 1] && f[i][j - 1]) {
                    f[i][j] = true;
                } else {
                    f[i][j] = false;
                }
            }
        }
        return f[len1][len2];  // 注意这里f数组的下标不是代表s1和s2数组中的下标，而是加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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class Solution {
    
    private int len1;
    private int len2;
    private int len3;
    private char[] c1;
    private char[] c2;
    private char[] c3;
    private char[][] f; // 0-未计算过  1-true   2-false
    
    private boolean search(int idx1, int idx2) {
        // 边界
        if (idx1 < 0 && idx2 < 0) {
            return true;
        }
        if (idx1 >= 0 && idx2 >= 0 && f[idx1][idx2] > 0) {
            return f[idx1][idx2] == 1;
        }
        if (idx1 >= 0 && c1[idx1] == c3[idx1 + idx2 + 1]) {
            if (search(idx1 - 1, idx2)) {
                if (idx1 >= 0 && idx2 >= 0) {
                    f[idx1][idx2] = 1;
                }
                return true;
            }
        }
        if (idx2 >= 0 && c2[idx2] == c3[idx1 + idx2 + 1]) {
            if (search(idx1, idx2 - 1)) {
                if (idx1 >= 0 && idx2 >= 0) {
                    f[idx1][idx2] = 1;
                }
                return true;
            }
        }
        if (idx1 >= 0 && idx2 >= 0) {
            f[idx1][idx2] = 2;
        }
        return false;
    }
    
    public boolean isInterleave(String s1, String s2, String s3) {
        len1 = s1.length();
        len2 = s2.length();
        len3 = s3.length();
        if (len1 + len2 != len3) {
            return false;
        }
        if (len1 == 0) {
            return s2.equals(s3);
        }
        if (len2 == 0) {
            return s1.equals(s3);
        }
        f = new char[len1 + 1][len2 + 1];
        c1 = s1.toCharArray();
        c2 = s2.toCharArray();
        c3 = s3.toCharArray();
        return search(len1 - 1, len2 - 1);
    }
}