主題
題目連結：
題目意譯：
給定字串 s1 、 s2 和 s3 ，判斷 s3 是否由 s1 與 s2 交錯而形成的。
兩個字串 s 和 t 的一個交錯為它們被分為多個非空子字串之結構，其滿足：
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| ≦ 1
而交錯為 s1 + t1 + s2 + t2 + s3 + t3 + …… 或是 t1 + s1 + t2 + s2 + t3 + s3 + ……
注： a + b 為字串 a 和 b 之串接。
限制：
0 ≦ s1.length 、 s2.length ≦ 100
0 ≦ s3.length ≦ 200
s1 、 s2 和 s3 由小寫字母組成。
進階： 你可以只使用 O(s2.length) 額外記憶體空間嗎？
範例測資：
範例 1：
輸入： s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
輸出： true
範例 2：
輸入： s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
輸出： false
範例 3：
輸入： s1 = "", s2 = "", s3 = ""
輸出： true
解題思維：
首先，如果 s1.length + s2.length ≠ s3.length，那當然 s3 不會是由 s1 和 s2 交錯而成。
（為了方便，以下字串的索引值皆從 1 開始數）
我們定義一一個二維陣列 D[i][j] ，其代表著 s1 的前 i 個字元以及 s2 的前 j 個字元是否可以交錯形成 s3 的前 i + j 個字元。因此可以看我們的所求即為 D[s1.length][s2.length] 。
我們可以看到初始狀態為
D[0][0] = true
D[i][0] = (D[i-1][0] 且 s1[i] == s3[i])，其中 i > 0
D[0][j] = (D[0][j-1] 且 s2[j] == s3[j])，其中 j > 0
而其遞迴式為
D[i][j] = (D[i-1][j] 且 s1[i] == s3[i + j]) 或
(D[i][j-1] 且 s2[i] == s3[i + j])
因此有了初始狀態以及遞迴式之後我們就可以像是經典的動態規劃（Dynamic Programming）般（如這題）推得 D[s1.length][s2.length] 。
而要只使用 O(s2.length) 額外記憶體空間的話，我們只需要將原本的二維陣列 D 改變成兩個一維的陣列 D1 、 D2 ，然後在求值的過程中交替使用這兩個陣列即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
