Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
題意：三個(gè)字符串s1所灸、s2、s3，s1和s2交叉拼接能否變成s3.
舉例：s1是ab涧团，s2是cd养交，則abcd件相、acbd蓄喇、cdab都是合法的拼接結(jié)果。
思路：
暴力的求解就是嘗試每一種可能的組合，然后與s3比較付材。即第一個(gè)字母可以選a或c朦拖，如果選好a，第二個(gè)字母可以從b厌衔、c中選璧帝，以此類(lèi)推，時(shí)間復(fù)雜度是2的(l1+l2)次方富寿，l1睬隶、l2分別代表s1和s2的長(zhǎng)度。
指數(shù)或階乘時(shí)間復(fù)雜度的解法页徐，一般都可以用動(dòng)態(tài)規(guī)劃來(lái)優(yōu)化苏潜。s1和s2要組合出s3的前兩個(gè)字母一共有三種方法：取s1的前兩個(gè)、s1和s2各取第一個(gè)变勇、s2取前兩個(gè)恤左，其中有一種可以就算可以。那么要拼出s3的前三個(gè)呢搀绣？只需要考慮在拼出前兩個(gè)字母的三個(gè)方案中飞袋，哪個(gè)方案可行并且s3的第三個(gè)字母和s1或s2的下一個(gè)字母相同就可以。
比如s3是acbd链患，s1和s2各取第一個(gè)可滿(mǎn)足s3前兩個(gè)字母巧鸭，并且s1的第二個(gè)字母和s3的第三個(gè)字母相同，所以成立麻捻。
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length()) {
return false;
}
boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 && j == 0) {
dp[i][j] = true;
} else if (i == 0) {
dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
} else if (j == 0) {
dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
} else {
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
}
}
}
return dp[s1.length()][s2.length()];
}