題目描述
給出三個字符串s1, s2, s3,判斷s3是否可以由s1和s2交織而成脖咐。
例如：
s1 ="aabcc",
s2 ="dbbca",
如果s3 ="aadbbcbcac", 返回true
如果s3 ="aadbbbaccc", 返回false
思路
動態(tài)規(guī)劃师崎，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];
}
}
