[LeetCode] Interleaving String - 交織的字符串
題目很明確就是判斷字符串s3是否可以由s1和s2交織組成。乍一看並不是很難，但是仔細一想並沒有那麼簡單。
第一個想法就是首先遍歷s1和s3，將s1中出現的字母在s3中刪除，然後再去比較剩下來的字符串是否與s2相同。但是很明顯這個想法是錯誤的，因為同樣的字母可能出現在s1和s2中，這樣子s3中某一個字母匹配的可能是s1中的也可能是s2中的，所以這種解法是錯誤的。
這道題目正確的解法之一是利用動態規劃，在列出答案之前先寫一下如何去思考這個問題。
思考路徑
從小規模的問題入手
首先，先將問題的規模縮小。縮到最小，假設s1和s2分別只有一個字符，那麼我們會怎麼去判斷s3是否由s1和s2交織而成呢？
例-1
假設s1 = "a", s2 = "b", 's3 = "ab"'。那麼我們的判斷邏輯大概會是這樣子：
如果s1的第一位和s3的第一位相同，則比較s2的第二位和s3的第二位，如果也相同則成立。
如果s2的第一位和s3的第一位相同，則比較s1的第二位和s3的第二位，如果也相同則成立。
沒有符合條件的，則不成立。
if (s1[0] == s3[0]){
if (s2[0] == s3[1]){
return true;
}
}
if (s2[0] == s3[0]){
if(s1[0] == s3[1]){
return true;
}
}
return false;
例-2 我們將規模稍微放大，假設s1 = "a", s2 = "bb", s3 = "abb"。我們來想想這個情況我們會怎麼處理呢？
按照上面的思路，寫出來的邏輯就是這樣子的：
if (s1[0] == s3[0]){
if (s2[0] == s3[1]){
if (s2[1] == s3[2]){
return true;
}
}
}
if (s2[0] == s3[0]){
if (s1[0] == s3[1]){
if (s2[1] == s3[2]){
return true;
}
}
if (s2[1] == s3[1]){
if (s1[0] == s3[2]){
return true;
}
}
return false;
}
但是如果想一想，我們只是在s2和s3後面加了一個字符，我們完全沒有必要重新開始判斷。我們在第一個例子中已經知道了s1 = "a", s2 = "b", 's3 = "ab"'的結果，我們如果這個結果不成立，我們就沒有必要再做判斷了。如果成立的話我們也只需要將新加進來的字符判斷一下就行了，如果相等則成立，不相等則不成立。這最大程度上的利用了已有的信息避免了重復的運算。
那我們嘗試把例-1中的信息保存下來，可以得到下面這個圖：
Case-1 matrix
這個二維數組中的某個元素matrix[i][j]的含義可以理解為：s1.substring(0,i)和s2.substring(0,j)這兩個字符串組成s3.substring(0,i+j-1)字符串的可能組合。那麼當s1或者s2任意一個字符串的長度增長的時候，我們只需要基於已有的可能性上再去比較新增加的字符即可。比如，上面的二維數組在例-2的情況下就演化為：
Case-2 matrix
從圖中很容易看出，當我們在s2中增加一個'b'的時候我們只需要計算martix[0][2]和martix[1][2]，而這兩個值分別是根據以後的數據演化出來的。matrix[0][1] => matrix[0][2], matrix[0][2] & matrix[1][1] => matrix[1][2]。
總結
從上面的兩個例子中我們可以得出，當某一個s1或s2中的某一個字符串增加一個字符的時候我們可以通過已有的數據推導出來新的結果集而不需要重新進行很多計算。所以我們可以將普通的字符串拆分成小規模的問題，通過這種累積的方式得到最終的結果。
而通過上面的那個矩陣，我們可以發現，如果我們想要知道字符串s3是否由s1和s2交織組成以及如何組成，我們需要算出一個$(len(s1) + 1) * (len(s2) + 1)$的矩陣，然後計算出matrix[len(s1)][len(s2)]的結果才能夠得到答案。
當我們有兩個字符串s1,s2的時候，我們將s1,s2當作和例-1中一樣只有一個字符為開始，然後保持s1或s2的長度不變，而慢慢增加另一個字符串的長度來慢慢填充這個矩陣。算出整個矩陣後就得到了我們需要的答案。
實踐
就拿s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"為例子，我們嘗試填充一個矩陣，它會是這樣子的：
full-case-matrix
題目只要求判斷結果，但是不需要列出可能的組合。所以我們其實沒有必要存放組合，而是直接存一個布爾值判斷是否有方案即可。
代碼如下：
public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null)
return false;
if (s1.length() + s2.length() != s3.length())
return false;
boolean[][] matrix = new boolean[s1.length() + 1][s2.length() + 1];
matrix[0][0] = true;
for (int i = 1; i <= s2.length(); i++) {
if (s2.charAt(i - 1) == s3.charAt(i - 1))
matrix[0][i] = true;
else
break;
}
for (int i = 1; i <= s1.length(); i++) {
if (s1.charAt(i - 1) == s3.charAt(i - 1))
matrix[i][0] = true;
else
break;
}
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1.charAt(i - 1) == s3.charAt(i + j - 1))
matrix[i][j] = matrix[i - 1][j] || matrix[i][j];
if (s2.charAt(j - 1) == s3.charAt(i + j - 1))
matrix[i][j] = matrix[i][j - 1] || matrix[i][j];
}
}
return matrix[s1.length()][s2.length()];
}
