面试算法96：字符串交织

题目

输入3个字符串s1、s2和s3，请判断字符串s3能不能由字符串s1和s2交织而成，即字符串s3的所有字符都是字符串s1或s2中的字符，字符串s1和s2中的字符都将出现在字符串s3中且相对位置不变。例如，字符串"aadbbcbcac"可以由字符串"aabcc"和"dbbca"交织而成。

分析

每步从字符串s1或s2中选出一个字符交织生成字符串s3中的一个字符，那么交织生成字符串s3中的所有字符需要多个步骤。每步既可能从字符串s1中选择一个字符，也可能从字符串s2中选择一个字符，也就是说，每步可能面临两个选择。完成一件事情需要多个步骤，而且每步都可能面临多个选择，这个问题看起来可以用回溯法解决。
这个问题并没有要求列出所有将字符串s1和s2交织得到字符串s3的方法，而只是判断能否将字符串s1和s2交织得到字符串s3。如果能够将字符串s1和s2交织得到字符串s3，那么将字符串s1和s2交织得到字符串s3的方法的数目大于0。这只是判断问题的解是否存在（即判断解的数目是否大于0），因此这个问题更适合应用动态规划来解决。
可以用函数f（i，j）表示字符串s1的下标从0到i的子字符串（记为s1[0…i]，长度为i+1）和字符串s2的下标从0到j的子字符串（记为s2[0…j]，长度为j+1）能否交织得到字符串s3的下标从0到i+j+1（记为s3[0…i+j+1]，长度为i+j+2）的子字符串。f（m-1，n-1）就是整个问题的解。
当s3[i+j+1]和s1[i]相同时，f（i，j）的值等于f（i-1，j）的值。类似地，当s3[i+j+1]和s2[j]相同时，f（i，j）的值等于f（i，j-1）的值。如果s1[i]和s2[j]都和s3[i+j+1]相同，此时只要f（i-1，j）和f（i，j-1）有一个值为true，那么f（i，j）的值为true。

解

public class Test {public static void main(String[] args) {boolean result = isInterleave("aabcc", "dbbca", "aadbbcbcac");System.out.println(result);}public static boolean isInterleave(String s1, String s2, String s3) {if (s1.length() + s2.length() != s3.length()) {return false;}boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];dp[0][0] = true;// 列为0，没有取用s2字符串的数字for (int i = 0; i < s1.length(); i++) {dp[i + 1][0] = s1.charAt(i) == s3.charAt(i) && dp[i][0];}// 行为0，没有取用s1字符串的数字for (int j = 0; j < s2.length(); j++) {dp[0][j + 1] = s2.charAt(j) == s3.charAt(j) && dp[0][j];}for (int i = 0; i < s1.length(); i++) {for (int j = 0; j < s2.length(); j++) {char ch1 = s1.charAt(i);char ch2 = s2.charAt(j);char ch3 = s3.charAt(i + j + 1);// 注意是dp[i + 1][j + 1]dp[i + 1][j + 1] = (ch1 == ch3 && dp[i][j + 1]) || (ch2 == ch3 && dp[i + 1][j]);}}return dp[s1.length()][s2.length()];}
}