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];
}
