Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
题意：
给定s1和s2，判断给定的s3是不是s1和s2交织相错后可以生成的字符串
思路：
遇到字符串的子序列或匹配问题巴普洛夫狗流哈喇子实验般的想到dp
s1 = 0 "a a b c c",
0 T
s2 = "d
b
b
c
a",
------------------------ s3 = "aadbbcbcac"
初始化:
dp[0][0] = true
考虑是否需要预处理第一个row： dp[0][j] ？ 需要！处理极端情况即s3的字符完全来自s1，则if s1.charAt(j-1) == s3.charAt(j-1) , dp[0][j] = dp[0][j-1]
考虑是否需要预处理第一个col ： dp[i][0] ？ 需要！处理极端情况即s3的字符完全来自s2，则if s2.charAt(i-1) == s3.charAt(i-1) , dp[i][0] = dp[i-1][0]
对于dp[i][j]
s3下一个字符，要么来自s1，要么来自s2
dp[i][j] = (dp [i-1][j] && s2.charAt(i-1) == s3.charAt(i + j -1) )
||(dp [i][j-1] && s1.charAt(j-1) == s3.charAt(i + j -1) );
【注意，之前错写成】
if s2.charAt(i-1) == s3.charAt(i + j -1), dp [i][j] = dp [i-1][j]
if s1.charAt(j-1) == s3.charAt(i + j -1), dp [i][j] = dp [i][j-1]
为何错？ 因为dp[i][j] 若此时等于'b' 而此时s1有'b' ， s2有'b', dp[i][j] 就会两个if语句都进入，最终被先后赋值两次。
代码：
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length()) return false;
boolean[][] dp = new boolean[s2.length() + 1][s1.length() + 1];
// init
dp[0][0] = true;
for(int i = 1; i<= s2.length(); i++){
if(s2.charAt(i-1) == s3.charAt(i-1)) {
dp[i][0] = dp[i-1][0];
}
}
for(int j = 1; j <= s1.length(); j++){
if(s1.charAt(j-1) == s3.charAt(j-1)) {
dp[0][j] = dp[0][j-1];
}
}
for(int i = 1; i<= s2.length(); i++){
for(int j = 1; j <= s1.length(); j++){
dp[i][j] = (dp [i-1][j] && s2.charAt(i-1) == s3.charAt(i + j -1) )
||(dp [i][j-1] && s1.charAt(j-1) == s3.charAt(i + j -1) );
}
}
return dp[s2.length()][s1.length()];
}
}