面试指南——字符串的交错组成

题目:
现在有3个字符串s1,s2,s3,我们需要判断s3是否是由s1和s2交错组成的。对于三个字符串A,B,C。我们称C由A和B交错组成当且仅当C包含且仅包含A,B中所有字符,且对应的顺序不改变
例如s1=”abc”,s=”1234d”,s3=”ab1234dc”,那么s3是由s1和s2交错组成的,如果s3=”ab1234cd”,则s3不是由s1和s2交错组成的。
/*
* str1长度为M,str2长度为N,
* aim由str1和str2组成,所以长度为M+N,如果长度不对的话返回false,生成m+1,n+1大小的Boolean类型dp矩阵,
* dp[i][j]的值代表aim[0…i+j-1]能否被str1[0…i-1]和str2[0…j-1]交错组成。
* 从左到右,从上到下计算dp矩阵,计算过程如下
* a.dp[0][0] = true;当aim为空时,可以被两个空串组成
* b.dp矩阵第一列即dp[0…M-1][0],dp[i][0]表示aim[0…i-1]能否只被str1[0…i-1]交错组成;
* 如果aim[0…i-1]==str1[0…i-1],dp[i][0]=true,否则为false;
* c.dp矩阵第一行即dp[0][0…N-1],dp[0][j]表示aim[0…j-1]能否只被str2[0…j-1]交错组成;
* 如果aim[0…j-1]==str2[0…j-1],dp[0][j]=true,否则为false;
* d.对于其他未知的dp[i][j]
* 1.dp[i-1][j]代表aim[0…i+j-2]能否被str1[0…i-2]和str2[0…j-1]交错组成,
* 如果可以,那么如果再有str1[i-1]等于aim[i+j-1],说明str1[i-1]可以作为交错组成aim[0…i+j-1]的最后一个字符,dp[i][j]=true
* 2.dp[i][j-1]代表aim[0…i+j-2]能否被str1[0…i-1]和str2[0…j-2]交错组成,
* 如果可以,那么如果再有str1[j-1]等于aim[i+j-1],说明str1[j-1]可以作为交错组成aim[0…i+j-1]的最后一个字符,dp[i][j]=true
* 3.如果以上两种情况都不满足,则dp[i][j]=false;
*
* 空间压缩方法
* 比较str1和str2长度较小的那个作为列对应的字符串,然后生成和较短字符串长度一样的一维数组dp,滚动更新即可。
*/

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class 字符串的交错组成 {
    public static boolean isCross1(String str1,String str2,String aim) {
        if(str1 == null || str2 == null || aim == null) {
            return false;
        }
        char[] ch1 = str1.toCharArray();
        char[] ch2 = str2.toCharArray();
        char[] chaim = aim.toCharArray();
        if(ch1.length + ch2.length != chaim.length) {
            return false;
        }
        boolean[][] dp = new boolean[ch1.length+1][ch2.length+1];
        dp[0][0] = true;
        for(int i = 1;i <= ch1.length;i++) {
            if(ch1[i-1] != chaim[i-1]) {
                break;
            }
            dp[i][0] = true;
        }
        for(int j = 1;j <= ch2.length;j++) {
            if(ch2[j-1] != chaim[j-1]) {
                break;
            }
            dp[0][j] = true;
        }
        for(int i = 1;i<=ch1.length;i++) {
            for(int j = 1;j<=ch2.length;j++) {
                if(ch1[i-1] == chaim[i+j-1] && dp[i-1][j] || ch2[j-1] == chaim[i+j-1] && dp[i][j-1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[ch1.length][ch2.length];
    }
    public static boolean isCross2(String str1, String str2, String aim) {
        if (str1 == null || str2 == null || aim == null) {
            return false;
        }
        char[] ch1 = str1.toCharArray();
        char[] ch2 = str2.toCharArray();
        char[] chaim = aim.toCharArray();
        if (chaim.length != ch1.length + ch2.length) {
            return false;
        }
        //选取ch1和ch2较短的一个,并初始化dp数组
        char[] longs = ch1.length >= ch2.length ? ch1 : ch2;
        char[] shorts = ch1.length < ch2.length ? ch1 : ch2;
        boolean[] dp = new boolean[shorts.length + 1];
        //初始化第一行dp数组
        dp[0] = true;
        for (int i = 1; i <= shorts.length; i++) {
            if (shorts[i - 1] != chaim[i - 1]) {
                break;
            }
            dp[i] = true;
        }
        //滚动更新
        for (int i = 1; i <= longs.length; i++) {
            dp[0] = dp[0] && longs[i - 1] == chaim[i - 1];
            for (int j = 1; j <= shorts.length; j++) {
                if ((longs[i - 1] == chaim[i + j - 1] && dp[j])
                        || (shorts[j - 1] == chaim[i + j - 1] && dp[j - 1])) {
                    dp[j] = true;
                } else {
                    dp[j] = false;
                }
            }
        }  
        return dp[shorts.length];
    }
   
    public static void main(String[] args) {
        String str1 = "1234";
        String str2 = "abcd";
        String aim = "1a23bcd4";
        System.out.println(isCross1(str1, str2, aim));
        System.out.println(isCross2(str1, str2, aim));

    }
}
0 条评论
发表一条评论