[程式設計] 17. Letter Combinations of a Phone Number
前言
這題是 LeetCode 17 題，要使用遞迴的技巧，題目請點這兒。
 |
| LeetCode 17 題的題目說明 |
這題是說舊手機的鍵盤上除了數字之外，還有英文字母。例如鍵盤 2 上有 "abc" 三個字母，鍵盤 3 上有 "def" 三個字母。
給一些數字，例如 23，列出可能的字串組合。在這個例中，可以列出 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] 這些組合。
這題如果限定給的數字有幾個，那可以用巢狀迴圈處理掉。但因為數字的個數未知，因此用「遞迴」是較好的作法。
這題所需要的遞迴技巧不高，是練習遞廻的好題目。
想法
想法可以用底下的圖來說明。下圖以使用者輸入 23 時為例。
因為一個數字就代表一個字母，所以 "23" 的長度為 2，因此輸出的結果的長度也為 2。因此，下圖中共有 2 個格子，第一個格子放 2 這個數字所代表的所有的字元的可能性，即 abc。
第二個格子就放 3 這個數字所代表的所有可能的字母，即 def。
由上圖可以看出，當第一層選 a 時，第二層有 d、e、f 這三種可能性，所以就組出 "ad"，"ae"，以及 "af" 這三個可能。
同理，當第一層選 b 時，第二層一樣有 d、e、f 這三種可能性，那就組出 "bd"，"be" 以及 "bf" 這三種。
依此類推。
開始寫程式
建立對照表
第一步是建立一個對照表，讓每一個數字，可以對應到它的字串。
tbl 是一個對照表，使用陣列來實作。之後我們可以透過
tbl[2] 就取得 2 這個數字所對應的字串，即 "abc"。
idx 代表目前的遞迴深度。
0 為第一次遞迴呼叫，
1 為第二次遞廻呼叫，
2 為第三次遞迴呼叫
依此類推。
digits 為使用者輸入的數字。若以前例而言， digits 為 "23"。
r 則代表結果字串。遞迴每次終止時， r 就代表一個可能的結果。
如果使用者只輸入兩個數字，如 23，那遞迴的深度為 2 (即兩次的遞廻呼叫)。所以如果 idx 為 2 時，代表這是第三次的遞迴呼叫，那代表可以終止了。
終止時，我們把結果字串 (即 r ) 推入 result 這個 vector 中，並返回。
變數 num 代表每次遞廻呼叫時，所要處理的數字。
假設使用者輸入 "23"。
那 idx == 0 時， num 便為 2。
idx == 1 時，num 便為 3。
idx == 2 時，終止遞迴呼叫！
接著就使用一個 for 迴圈，走訪字串的每個字元。
每掃到一個字元，就將字元填到 r 中對應的位置，之後進入下一個遞迴呼叫。
tbl[2] 就取得 2 這個數字所對應的字串，即 "abc"。
遞迴函式
接著就是撰寫遞迴函式。函式的想法如前所示，底下是程式碼。idx 代表目前的遞迴深度。
0 為第一次遞迴呼叫，
1 為第二次遞廻呼叫，
2 為第三次遞迴呼叫
依此類推。
digits 為使用者輸入的數字。若以前例而言， digits 為 "23"。
r 則代表結果字串。遞迴每次終止時， r 就代表一個可能的結果。
終止條件
第 3 行到第 7 行是終止條件。如果使用者只輸入兩個數字，如 23，那遞迴的深度為 2 (即兩次的遞廻呼叫)。所以如果 idx 為 2 時，代表這是第三次的遞迴呼叫，那代表可以終止了。
終止時，我們把結果字串 (即 r ) 推入 result 這個 vector 中，並返回。
遞迴呼叫
第 10 到 16 行為遞迴呼叫的部分。變數 num 代表每次遞廻呼叫時，所要處理的數字。
假設使用者輸入 "23"。
那 idx == 0 時， num 便為 2。
idx == 1 時，num 便為 3。
idx == 2 時，終止遞迴呼叫！
接著就使用一個 for 迴圈，走訪字串的每個字元。
每掃到一個字元，就將字元填到 r 中對應的位置，之後進入下一個遞迴呼叫。
留言
張貼留言