面试算法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()];
    }
}