一、遞迴 (Recursion)
（一）概念
 |
| DFS遞迴法去模擬樹狀結構 |
題意為給一串輸入 (input)字串和一串目標 (target)字串，計算出目標字串在數入字串有多少種配對？上圖是利用DFS遞迴法去模擬樹狀結構。基本的概念為，先紀錄目標字串在輸入字串中的位置 (target & index)，可知b會出現在1, 3, 5、a會出現在2, 6、g會出現在4, 7, 8。接下來利用樹狀圖去枚舉出所有可能的bag位置排列，合法的output位置必為嚴格遞增數列，因此可以剪掉不合法的解，剩餘合法解即為答案（有9種）。
（二）實作
 |
| DFS遞迴法的架構 |
第一部分先紀錄目標字串在輸入字串中的位置 (letter table)，第二部分將目標字串 -> ASCII -> index of letter table，即為A-Z (0-25)、a-z (26-53)。第三部分計算合法的排列數。
 |
| DFS遞迴去模擬樹狀結構 |
permutation()有五個參數，分別為count計算合法解數；target為轉換為index的目標字串；letter為輸入字串的字元位置；level為樹的階層；pre為上一個搜尋到的位置。
permutation中有兩種情況，一種為level到達底層時，計算合法解；另一種為level尚未到底層時，比較這層和下層的值，如果這層值<下層值，則展開遞迴並且終止j迴圈，進入下一個i迴圈。為了要保持遞迴的連貫性，並需告知下一個遞迴，上次我搜尋到第j (pre)個，請從第pre個開始搜尋。當下層遞回結束後，回到上層時，由於j的搜尋早已在下層遞回搜尋完畢，故j迴圈直接停止，避免重複搜索。
（三）時間複雜度
S為輸入字串長度，T為目標字串長度。這方法最佳的情況為輸入和目標字串其字元分佈相當平均時，也就是每層展開的節點數皆為S/T，樹高為T，樹底為(S/T)^T，故為T*(S/T)^T。最差的情況則為輸入和目標字串其字元分佈相當不平均時，也就是每層展開的節點數皆為S，故為T*S^T。顯然這方法受目標字串長度T有很大的影響，而且是指數型成長的，效能不是很好。
二、動態規劃 (Dynamic programing, DP)
（一）概念
 |
| 動態規劃 (Dynamic programing, DP) |
上圖為DP的方法，DP(i, j)代表target[1~j]在input[1~i]的最大配對數，故右手邊的DP table，最右下角即為bag在babgbagg的最大配對數。左上方有DP的遞迴關係式，第一行為初始化，灰色區塊分別初始化為1或0；第二行為如果字元相等，則將左上與上方相加並給予下方DP(i, j)；第三行為如果字元不相等，則將上方值直接給予下方。
（二）實作
 |
| DP 程式碼 |
第一部分先創建(n+1)x(m+1) DP table並做初始化的工作，第二部分直接DP遞回關係式的規則，最後回傳DP[n][m]即為答案。實作時s為0~n-1，t為0~m-1，故比對時是比對s[i-1]和t[i-1]。
（三）時間複雜度
S為輸入字串長度，T為目標字串長度，則DP時間複雜度為O(ST)，是多項式成長。效能上DP比DFS遞迴來得好，在LeetCode的評分上，DP方法有通過測試，而DFS遞迴因為時間過長而沒有通過測試。
留言
張貼留言