子序列——字符串是否由两个字符串交错构成（八）

LeetCode_97_InterleavingString

题目分析：

  Ø d b b c a
Ø T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T
横向扫描，也就是对于s3中每次新增的字符，s1或者s2中任意一个能取出来匹配就是T，否则F。
也就是上方或者左方至少一个为T就是T。
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i - 1 + j))
           ||
           (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1 + i));
初始项dp[0][0]为true,因为此刻s1,s2,s3都是空串。
然后第一列和第一行分别比较对应s1和s3对应位置的值，如果相等就是T，
如果产生任何一个不相等，之后的都不相等。

解法：

public static boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length() + s2.length() != s3.length()) return false;
    int n1 = s1.length();
    int n2 = s2.length();
    boolean[][] dp = new boolean[n1 + 1][n2 + 1];
    dp[0][0] = true;
    for (int i = 1; i <= n1; ++i) {
        dp[i][0] = dp[i - 1][0] && (s1.charAt(i - 1) == s3.charAt(i - 1));
    }
    for (int i = 1; i <= n2; ++i) {
        dp[0][i] = dp[0][i - 1] && (s2.charAt(i - 1) == s3.charAt(i - 1));
    }
    for (int i = 1; i <= n1; ++i) {
        for (int j = 1; j <= n2; ++j) {
            dp[i][j] =
                    (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i - 1 + j))
                    ||
                    (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1 + i));
        }
    }
    return dp[n1][n2];
}