字符串的交错组成

给定三个字符串str1、str2和aim。如果aim包含且仅包含来自str1和str2的所有字符，而且在aim中属于str1的字符之间保持原来在str1中的顺序，属于str2的字符之间保持原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是否是str1和str2交错组成。
str1=“AB”，str2=“12”。那么“AB12”、“A1B2”、“A12B”、“1A2B”和“1AB2”等等都是str1和str2交错组成。

思路 && 代码

经典动态规划

如果str1的长度为M， str2的长度为N，经典动态规划的方法可以达到时间复杂度O(M*N)，额外空间复杂度O(M*N)。

首先aim如果是str1和str2的交错组成， aim的长度一定是M+N，否则直接返回false。
然后生成大小为(M+1)*(N+1)布尔类型的矩阵dp。
dp[i][j]的值代表aim[0..i+j-1]能否被str1[0..i-1]和str2[0..j-1]交错组成。

计算dp矩阵的时候，是从左到右再从上到下的计算的， dp[M][N]就是dp矩阵中最右下角的值，
就表示aim整体能否被str1整体和str2整体交错组成，也就是最终结果。具体说明dp矩阵每个位置的值是如何计算。

1， dp[0][0]=true。 aim为空串时，当然可以被str1为空串和str2为空串交错组成。
2，矩阵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，否则令dp[i][0]=false。
3，矩阵dp第一行即dp[0][0..N-1]。 dp[0][j]表示aim[0..j-1]能否只被str2[0..j-1]交错组成。
如果aim[0..j-1]等于str1[0..j-1]，则令dp[i][0]=true，否则令dp[i][0]=false。
4，对于其他位置(i,j)， 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]交错组成，如果可以，
那么如果再有str2[j-1]等于aim[i+j-1]，说明str1[j-1]可以作为交错组成aim[0..i+j-1]的最
后一个字符。令dp[i][j]=true。
3）如果情况1）和情况2）都不满足，令dp[i][j]=false。
具体过程请参看如下代码中的isCross1方法。

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
public static boolean isCross1(String str1, String str2, String aim) {
	if (str1 == null || str2 == null || aim == null) {
		return false;
	}
	char[] char1 = str1.toCharArray();
	char[] char2 = str2.toCharArray();
	char[] caim = aim.toCharArray();
	if (char1.length + char2.length != caim.length) {
		return false;
	}
	// 多增加一行和一列，为空值，方便计算
	int row = char1.length + 1;
	int col = char2.length + 1;
	boolean[][] dp = new boolean[row][col];
	dp[0][0] = true;
	for (int i = 1; i < row; i++) {
		// str1[0,i-1]交错aim[0,i-1]
		if(char1[i-1] != caim[i-1]){
			//遇到不等就退出循环，初始化时是false
			break;
		}
		dp[i][0] = true;
	}
	for (int i = 1; i < col; i++) {
		// str2[0,i-1]交错aim[0,i-1]
		if(char2[i-1] != caim[i-1]){
			break;
		}
		dp[0][i] = true;
	}
	
	for (int i = 1; i < row; i++) {
		for (int j = 1; j < col; j++) {
			if (caim[i + j - 1] == char1[i - 1] && dp[i - 1][j]
					|| caim[i + j - 1] == char2[j - 1] && dp[i][j - 1]) {
				dp[i][j] = true;
			}
		}
	}
	return dp[row - 1][col - 1];
}

经典动态规划方法结合空间压缩的方法。

如果结合空间压缩的技巧可以把额外空间复杂度减至O(min{M,N})。
实际进行空间压缩的时候，比较str1和str2哪个长度较小，长度较小的那个作为列对应的字符串，
然后生成和较短字符串长度一样的一维数组dp，滚动更新即可。
具体请参看如下代码中的isCross2方法。

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
//压缩空间，只用一行表示一个数组，然后滚动更新
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;
	}
	//选出长短，长的在外循环，短的在循环内，因为使得不断更新短的数值
	char[] longs = ch1.length >= ch2.length ? ch1 : ch2;
	char[] shorts = ch1.length < ch2.length ? ch1 : ch2;
	boolean[] dp = new boolean[shorts.length + 1];
	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++) {
			//此时只更新到j-1，而j还没有更新，表示的是上一行的j值，即要更新位置的上面
			//j-1已经更新，表示的是要更新位置的左边
			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];
}