递归与动态规划——字符串的交错组成

Posted on | In ,

题目：给定3个字符串str1、str2和aim，如果aim包含来自str1和str2的所有字符，而且在aim中属于str1的字符之间保持在str1中的顺序，属于str2的字符之间保持在str2中的顺序，则成aim是由str1和str2交错组成的。

str1长度为M，str2长度为N，则aim长度应该为M+N，生成(M+1)*(N+1)的布尔类型动态规划矩阵dp，dp[i][j]表示aim[0,…i+j-1]能否被str1[0,..i-1]和str2[0,..j-1]交错组成。
注意：这里为什么加了一行和一列空字符串。如果不加，如对第一列dp[i][0]，表示aim[0,..i]能否被str1[i]和str2[0]交错组成，而dp[0][0]已经有str2[0]了，而aim其实可以只由一个字符串组成的，这种情况会导致分析不完全。

实现：

  1. 对于dp[0]][0]，表示aim为空时，能否被空串str1[0]和str2[0]组成，则dp[0]][0]=true
  2. 对于第一列dp[0,..M-1][0]，dp[i][0]表示aim[0,..i-1]能否只被str1[0,…i-1]组成。如果aim[0,..i-1]==str1[0,…i-1]，则返回true，否则返回false.
  3. 对于第一列dp[0][j]，情况与第一行类似，如果aim[0,…j-1]能够只被str2[0,..j-1]组成，则返回true，否则返回false。
  4. 对于非第一行和第一列，可能有以下3种情况之一：
    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[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]，表示str2[j-1]又可作为aim[i+j-1]的最后一个交错字符，则dp[i][j]=true。
    3）如果以上两种情况都不满足，则dp[i][j]=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
public class IsCross {
	public boolean isCross(String aim, String str1, String str2) {
		if (aim.length() != str1.length() + str2.length()) {
			return false;
		}
		int m = str1.length();
		int n = str2.length();
		boolean[][] dp = new boolean[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0 ; j < n; j++) {
				if (i == 0 && j == 0) {
					dp[i][j] = true; //都为空串，可以组成
				} else if (j == 0) {
					//aim[0,...i-1]可以是否只由str1[0,..i-1]组成，str1之前是交错的，如果str2[i-1]==aim[i+j-1]则返回true
					dp[i][j] = dp[i-1][j] && str1.charAt(i-1)==aim.charAt(i+j-1);
				} else if (i == 0) {
					//aim[0,...j-1]可以是否只由str2[0,..j-1]组成，str2之前是交错的，如果str2[i-1]==aim[i+j-1]则返回true
					dp[i][j] = dp[i][j-1] && str2.charAt(j-1)==aim.charAt(i+j-1);
				} else {
					//str1和str2都不为空。
					//从位置(i-1,j)到达(i,j)，如果在(i-1,j)时交错的，并且在i处与当前aim一致，则返回true；
					//从位置(i,j-1)到达(i,j)，如果在(i,j-1)时交错的，并且在j处与当前aim一致，则返回true.
					dp[i][j] = dp[i-1][j] && str1.charAt(i-1)==aim.charAt(i+j-1) 
							|| dp[i][j-1]&&str2.charAt(j-1)==aim.charAt(i+j-1);
				}
			}
		}
		return dp[m-1][n-1];
	}
1
2
3
4
5
6
7
8
9
	//Test
	public static void main(String[] args) {
		IsCross ic = new IsCross();
		String str1 = "AB";
		String str2 = "12";
		String aim = "A1B2";
		System.out.println(aim + "是否由" + str1 + "和" + str2 + "交错组成：" + ic.isCross(aim, str1, str2));
	}
}