題目
給出三個字符串:s1、s2、s3，判斷s3是否由s1和s2交叉構(gòu)成
樣例
比如 s1 = "aabcc" s2 = "dbbca"
當(dāng) s3 = "aadbbcbcac"，返回 true.
當(dāng) s3 = "aadbbbaccc"静秆， 返回 false.
分析
這道題可以用動態(tài)規(guī)劃的思想解決。
dp[i][j]：表示s1的前i個字符和s2的前j個字符是否由交叉構(gòu)成巡李。
顯然對于i+j個字符抚笔，要么等于s1的第i個，要么等于s2的第j個
- 當(dāng)?shù)扔趕1的第i個時侨拦，那么必須dp[i-1][j]是true,也就是前面i+j-2個字符是由交叉構(gòu)成的殊橙，那么加進(jìn)來的就為true
- 同理對于等于s2的第j個也是。
初始條件狱从，當(dāng)j=0時膨蛮，那么s1與s3每個字符相等的話，就為true
同樣當(dāng)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()];
}
}
