题目描述
给出三个字符串s1, s2, s3,判断s3是否可以由s1和s2交织而成。
例如：
s1 ="aabcc",
s2 ="dbbca",
如果s3 ="aadbbcbcac", 返回true
如果s3 ="aadbbbaccc", 返回false
思路
动态规划，dp[i][j]表示s1前i个字符和s2前j个字符是否能交织组成s3前i+j个字符。初始dp[0][0]=true；dp[i][0]的递推如下：如果dp[i-1][0]==true同时s1的第i个字符与s3的第i个字符相等，则dp[i][0]=true。dp[0][j]也同理。
更一般的情况dp[i][j]的递推如下：
dp[i-1][j]==true并且s1[i-1]==s3[i+j-1]
或者：
dp[i][j-1]==true并且s2[j-1]==s3[i+j-1]
则dp[i][j]=true
代码
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if (len1+len2!=len3) return false;
boolean[][] dp = new boolean[len1+1][len2+1];
dp[0][0] = true;
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
char[] str3 = s3.toCharArray();
for (int i=1; i<=len1; i++){
dp[i][0] = str1[i-1] == str3[i-1] && dp[i-1][0];
}
for (int j=1; j<=len2; j++){
dp[0][j] = str2[j-1] == str3[j-1] && dp[0][j-1];
}
for (int i=1; i<=len1; i++){
for (int j=1; j<=len2; j++){
dp[i][j] = (dp[i-1][j] && str3[i+j-1] == str1[i-1])
|| (dp[i][j-1] && str3[i+j-1] == str2[j-1]);
}
}
return dp[len1][len2];
}
}
