題目：

給定一個僅包含數字?2-9?的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

?解法一（哈希表+動態添加）：

將電話號碼中數字到字母的映射保存至哈希表中，遍歷輸入digits字符串中的每個字符，逐個添加所有等可能的組合情況，如下為筆者代碼：

class Solution {
public:vector<string> letterCombinations(string digits) {int length = digits.size();vector<string> result;unordered_map<char, string> hashTable1;hashTable1['1'] = "";hashTable1['2'] = "abc";hashTable1['3'] = "def";hashTable1['4'] = "ghi";hashTable1['5'] = "jkl";hashTable1['6'] = "mno";hashTable1['7'] = "pqrs";hashTable1['8'] = "tuv";hashTable1['9'] = "wxyz";//遍歷digits字符串中的所有字符for(char c:digits){string s = hashTable1[c];if(result.empty() && s!=""){for(char cc:s){string in_string(1, cc);result.push_back(in_string);}continue;}if(s!=""){int a = result.size();int b = s.size();//根據已有result容器中的字符串結果和此時輸入數字對應的字符串字母s，確定容器中新增的字符串for(int i =0; i<b-1; i++){for(int j=0; j<a; j++){result.push_back(result[j]);}}int num = 0;//遍歷字符串s，將字符串s中字符與result中現存字符串進行組合，更新得到添加后的新字符串for(char d:s){for(int i=0; i<a; i++){result[num+i] = result[num+i]+d;}num += a;}}}return result;}
};

解法二（回溯算法）：

首先使用哈希表存儲每個數字對應的所有可能的字母，然后進行回溯操作。

回溯過程中維護一個字符串，表示已有的字母排列（如果未遍歷完電話號碼的所有數字，則已有的字母排列是不完整的）。該字符串初始為空，每次取電話號碼的一位數字，從哈希表中獲得該數字對應的所有可能的字母，并將其中的一個字母插入到已有的字母排列的后面，然后繼續處理電話號碼的后一位數字，直到處理完電話號碼中的所有數字，即得到一個完整的字母排列。然后進行回退操作，遍歷其余的字母排列。

回溯算法用于尋找所有的可行解，如果發現一個解不可行，則會舍棄不可行的解。在這道題中，由于每個數字對應的每個字母都可能進入字母組合，因此不存在不可行的解，直接窮舉所有的解即可。實現代碼如下所示：

class Solution {
public:vector<string> letterCombinations(string digits) {vector<string> combinations;if (digits.empty()) {return combinations;}unordered_map<char, string> phoneMap{{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};string combination;backtrack(combinations, phoneMap, digits, 0, combination);return combinations;}void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {if (index == digits.length()) {combinations.push_back(combination);} else {char digit = digits[index];const string& letters = phoneMap.at(digit);for (const char& letter: letters) {//添加string字符串類型的combination最頂部的那個字符元素combination.push_back(letter);//調用遞歸函數，進行枚舉遍歷（終止條件是index索引值==digits字符串長度）backtrack(combinations, phoneMap, digits, index + 1, combination);//去除string字符串類型的combination最頂部的那個字符元素combination.pop_back();}}}
};

時間復雜度：O(3m×4n)，其中 m 是輸入中對應 3 個字母的數字個數（包括數字 2、3、4、5、6、8），n 是輸入中對應 4 個字母的數字個數（包括數字 7、9），m+n 是輸入數字的總個數。當輸入包含 m 個對應 3 個字母的數字和 n 個對應 4 個字母的數字時，不同的字母組合一共有 3m×4n 種，需要遍歷每一種字母組合。空間復雜度：O(m+n)，其中 m 是輸入中對應 3 個字母的數字個數，n 是輸入中對應 4 個字母的數字個數，m+n 是輸入數字的總個數。除了返回值以外，空間復雜度主要取決于哈希表以及回溯過程中的遞歸調用層數，哈希表的大小與輸入無關，可以看成常數，遞歸調用層數最大為 m+n。

筆者小記：

1、vector<string>& combinations；const unordered_map<char, string>& phoneMap；const string& digits；string& combination中 “&” 符號表示傳遞的引用，數據對象本身可以隨著引用值的修改一起修改。

2、combination.pop_back()中的.pop_back()函數，表示將conbination字符串類型的對象去除容器頂部的一個字符類型元素。

3、遞歸與回溯的區別：在函數中調用自身的方法稱為遞歸，遞歸函數需要確定遞歸函數的參數和返回值、確定遞歸函數的終止條件，確定單層遞歸的邏輯（確定每一層遞歸需要處理的信息，在這里也會重復調用自己來實現遞歸的過程）。回溯函數可以理解成多分支的遞歸，主要是遞歸+局部暴力枚舉來實現（回溯有剪枝的功能，去掉那些不必要的遞歸）。回溯算法需要確定回溯函數模版返回值以及參數，回溯函數終止條件，回溯搜索的遍歷過程【（回溯法一般是在集合中遞歸搜索（for循環，一個節點有多少個孩子，就執行多少次），集合的大小構成了樹的寬度，遞歸的深度構成了樹的深度）】