1. 題目解析
題目鏈接：電話號碼的字母組合
這個問題的理解其實相當簡單，只需看一下示例，基本就能明白其含義了。
2.算法原理
算法設計思路
在解決這類問題時，我們需要認識到每個位置上的數字對應的字符集合是相互獨立的，即一個位置上的字符選擇不會影響到其他位置上的字符選擇。基于這一觀察，我們可以采用回溯法來構建所有可能的字符組合。
關鍵數據結構
首先，我們需要一個字典（在C++中可以使用unordered_map）來存儲每個數字對應的字符集合。這個字典我們稱之為phoneMap，其中鍵是數字（字符型），值是該數字對應的所有可能字符組成的字符串。
遞歸函數設計
接下來，我們定義一個遞歸函數backtrack來構建所有可能的字符組合。該函數需要接受三個參數：
phoneMap：數字到字符集合的映射字典。digits：輸入的電話號碼字符串，其中包含的數字需要被轉換為字符組合。index：當前正在處理的數字在digits中的索引。
函數內部不需要額外的返回值（可以使用void），但需要一些額外的數據結構來保存中間狀態和最終結果。這里我們使用一個字符串ans來保存當前的字符組合狀態，以及一個容器（比如vector<string>）來保存所有有效的字符組合結果。
遞歸流程
-
遞歸結束條件：當
index等于digits的長度時，說明我們已經處理了所有的數字，此時ans中保存的就是一個有效的字符組合。我們將ans加入到結果容器中，并返回上一層遞歸。 -
處理當前數字：從
digits中取出當前索引index對應的數字digit，然后根據phoneMap找到對應的字符集合letters。 -
遍歷字符集合：對于
letters中的每一個字符letter，我們執行以下操作：- 將
letter添加到當前的字符組合ans的末尾。 - 遞歸調用
backtrack函數，傳入index + 1作為下一個要處理的數字的索引。 - 在遞歸調用返回后，我們需要將剛剛添加到
ans末尾的letter刪除，以進行回溯，嘗試其他可能的字符。
- 將
-
返回結果：當所有的遞歸調用都完成后，我們的結果容器中就已經保存了所有可能的字符組合。最后，我們返回這個結果容器即可。
tips:
- 在遞歸過程中，我們需要確保每次遞歸調用都是基于當前狀態的獨立副本，以避免修改原始數據或產生意外的副作用。
- 由于遞歸的深度可能很大（特別是當輸入的電話號碼很長時），我們需要確保遞歸的實現是高效且沒有棧溢出的風險的。在某些情況下，可能需要考慮使用迭代或顯式的棧結構來替代遞歸。
- 為了代碼的可讀性和可維護性，我們應該盡量將邏輯拆分成小的、可重用的函數或方法，并添加適當的注釋和文檔。
3.代碼編寫
class Solution {string hash[10] = {"", "", "abc", "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};string path;vector<string> ret;public:vector<string> letterCombinations(string digits) {if(digits.size() == 0) return ret;dfs(digits, 0);return ret;}void dfs(string& digits, int pos){if(pos == digits.size()){ret.push_back(path);return;}for(auto& ch : hash[digits[pos] - '0']){path.push_back(ch);dfs(digits, pos + 1);path.pop_back();}}
};The Last
嗯，就是這樣啦，文章到這里就結束啦，真心感謝你花時間來讀。
覺得有點收獲的話，不妨給我點個贊吧！
如果發現文章有啥漏洞或錯誤的地方，歡迎私信我或者在評論里提醒一聲~
