Leetcode 解題紀錄 97. Interleaving String
題目
給定三個字串 s1 s2 與 s3，判斷 s3 是否由 s1 與 s2 的字元彼此交錯重組而成，順序不能改變
限制
- s1 與 s2 字元數介於 1~100，s3 介於 1~200。皆為小寫字元
觀察
- 順序不能改變，所以比對只會是從前到後
- 由於是重組，s3 不能有 s1 與 s2 以外的字元出現
- 條件中 s3 沒有說必須等於 s1+s2 來看，預期會有這樣的 corner case
- 逐一比對 s1 與 s3 的字元，如果有不屬於 s1 的字元，那就一定是 s2 的或是不合法
- 如果 s1 與 s2 的字元沒有重複，那這個問題就會非常簡單，因此兩者重複的字元才是關鍵，重複的字元給 s1 與 s2 的結果會不同，會需要兩者都嘗試，可能是 DFS/BFS，因為只要有一條路徑抵達即可所以選用 DFS
思路
- 由於 s3 應該要包含所有 s1 的字元，先拿 s1 與 s3 逐一字元比對，試著拿走符合 s1 所有字元的各種組合，在拿剩下的字元與 s2 比對看是否符合，只要有一個符合就算正確
Trial 1
- 使用 DFS， 設計一個遞迴程式比對 s1 與 s3
- 從 s1 第一個字元開始，在 s3 中依序找符合的字元
- 如果不符合，代表這個字元可能屬於 s2，跳過它
- 如果符合，試著標記這個字元並移動 s1 指標與 s3 指標到下個字元，執行下一層遞迴
- 如果遞迴的結果最後不成功，可能這個字元屬於 s2 ，取消標記試試看能不能找到下個符合的字元
- 停止條件為 s1 的指標移動到底，代表 s1 字元已經找完，拿掉標記屬於 s1 的字元重新組成字串，看看能不能等於 s2，如果可以則回傳 True.
這算是暴力解，最糟糕的情形，時間複雜度應該是 n 階層，n 是 s1 的長度。
果不其然，submit 後在 99/106 的TC TLE了，這樣的解法不是可接受的。
Trial 2
試著用遞迴的方式，把大問題分解成較小的問題
- 比對 s1 與 s2 的第一個字元，如果不符合，看看 s3 的第一個字元跟誰一樣。假設跟 s1 的第一個字元相同，那就把 s1 與 s3 各拿掉一個字元成為新的字串，變成一個更小的問題。如果是 s2 ，就拿掉 s2 與 s3 的第一個字元遞迴下去。
- 如果相同則是產生兩個小的子問題(上面的兩個 case)，看看哪一個會成功
- 停止條件為 s1 或 s2 為空字串，s3 等於另外一個字串的話，代表比對成功
假設每次都產生兩個子問題，那時間複雜度會是 2 的(m+n)次方，進步了一點點，這次有多過了幾個 TC，後面還是 TLE
Trial 3
在這些遞迴中很多是重複的，因此可以使用 memoization 來避免，遞迴的狀態只在於 s1 與 s2 的內容，因此用 s1 與 s2 的組合當作 key，利用 Map 來紀錄做過的結果。
經過改善，加上 memo 的版本終於通過了所有的 TC，由於不會執行重複的步驟，時間複雜度與 m*n 有關，空間複雜度應該是 (m*n) 的2次方，因為每次都產生新的字串(m-1)或(n-1)與 (m+n-1)，這部份可由傳遞字串陣列與指標來改善，不過程式碼會變得比較多。雖然是通過所有 TC，結果是很慘烈的敬陪末座，離最佳解蠻遠的
最佳解
通常遞迴加上 memorization 都可能用 DP 來解，自己想了很久還是不知道 table 要怎麼建，只好去看解答，看了很久才終於了解它的意思，先說表格的建立方式，它是以 s1 與 s2 當作行與列，試著組合出 s3 。
先看最簡單的 case，假設 s1(xyz) 與 s2(abc) 沒有重複的字元，從 B2 (空字串)開始走，s3 (B7)的第一個字元是 a ，比對 s1 與 s2 在的第一個字元後，知道是 s2 符合，那就只能先往右走到 C2，接著看第二個字元是 x，比較 s2的第二個字元(b) 以及s1的第一個字元(x)，那就是往下走拿走x，再往下拿y…依序最後走到 z 。
另外一個 case，只要 s3 是正確的，就一定能走到右下角，而且只會有一種走法。
這個問題變成走棋盤問題，看能不能從左上到右下能否走完，因為s1 與 s2 的字元順序不能改變，且不能重複使用字元，所以每一格只能走下或右，每一格會對應到兩個字母，要看上個位置來決定目前的字母是那一個，從左邊來的就是拿 s2，從上方來的就是拿 s1。
如果要列舉所有可能走到右下角的路線，看看那一條符合 s3，那會有 m*n 的 2 次方個，但是實際上當有行不通的路線就可以不用往下走了。
依照這樣的思考方式，我們可以知道在檢查任何一個位置時，不管它是怎麼走到這裡來的，這個位置一定對應到 s3 的特定位置，例如在 row 1，col2的字元，一定是對應到 s3 第3(1+2)個字元，它是走那條路線(右下右或右右下)到這個位置的並不影響這個結果。
這個字元必須來自 s1 的第一個字元或是 s2 的第二個字元，如果都不是那這條路是錯的，標記為 False。
如果是等於s1，根據上面的例子，它必須是從上方一列來的，如果是 s2 那就是從左邊一列來的，如果上個位置是不能走到的，那這個位置就算有符合的字元也是錯的，因此要檢查上個位置是否也是合法。
因為每次都要檢查左邊或是上方，因此建立表格要從左上方開始建立，兩個字串前面各加一排作為空字元，左上角 (0,0) 的位置就是空字串設定為 True，代表一定可以從空字串開始，開始從左往右，從上到下比對。
程式碼很簡單，要注意的是因為 s1，s2 與 s3 前面都多了一個空字元，取得字元時指標要減一
