题目:
现在有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,滚动更新即可。
*/
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)); } }