题目
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成
样例
比如 s1 = "aabcc" s2 = "dbbca"
当 s3 = "aadbbcbcac"，返回 true.
当 s3 = "aadbbbaccc"， 返回 false.
分析
这道题可以用动态规划的思想解决。
dp[i][j]：表示s1的前i个字符和s2的前j个字符是否由交叉构成。
显然对于i+j个字符，要么等于s1的第i个，要么等于s2的第j个
- 当等于s1的第i个时，那么必须dp[i-1][j]是true,也就是前面i+j-2个字符是由交叉构成的，那么加进来的就为true
- 同理对于等于s2的第j个也是。
初始条件，当j=0时，那么s1与s3每个字符相等的话，就为true
同样当i=0时，也是一样！
代码
public class Solution {
/**
* Determine whether s3 is formed by interleaving of s1 and s2.
* @param s1, s2, s3: As description.
* @return: true or false.
*/
public 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;
for(int i=1;i<=s1.length();i++)
if(s3.charAt(i-1) == s1.charAt(i-1) && dp[i-1][0])
dp[i][0] = true;
for(int i=1;i<=s2.length();i++)
if(s3.charAt(i-1) == s2.charAt(i-1) && dp[0][i-1])
dp[0][i] = true;
for(int i=1;i<=s1.length();i++) {
for(int j=1;j<=s2.length();j++) {
if((s3.charAt(i+j-1) == s1.charAt(i-1) && dp[i-1][j]
)|| (s3.charAt(i+j-1) == s2.charAt(j-1) &&dp[i][j-1]))
dp[i][j] = true;
}
}
return dp[s1.length()][s2.length()];
}
}
