題目：

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

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

---

方法一：深度優先搜索，回溯

遞歸函數

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

.

class Solution(object):def letterCombinations(self, digits):""":type digits: str:rtype: List[str]"""if not digits: #空字符串，則返回空列表 return []phonemap={  #映射數字到對應的字母"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":'wxyz',}def backtrack(index): #回溯函數 ,處理當前的數字位置if index==len(digits):combinations.append("".join(combination))#將當前combination中的字母組合成字符串，加入 combinations 結果列表else:  #處理當前數字對應的所有可能字母digit=digits[index]  #取出當前 index 位置的數字for letter in phonemap[digit]:#遍歷當前數字 digit 對應的所有字母,2對應“a","b","c"combination.append(letter) #將當前 letter 加入 combination，表示選擇該字母backtrack(index+1)#遞歸調用 ,處理下一個數字的字母組合combination.pop()#回溯：撤銷當前選擇的字母，嘗試下一個可能的字母combination=[]#存儲當前選擇的字母combinations=[]#用于存儲所有可能的字母組合結果backtrack(0)return combinations #所有可能的字母組合

時間復雜度：O(3 **m?×4 **n?)，其中 m 是輸入中對應 3 個字母的數字個數（包括數字 2、3、4、5、6、8），n 是輸入中對應 4 個字母的數字個數（包括數字 7、9），m+n 是輸入數字的總個數。

空間復雜度：O(m+n)，其中 m 是輸入中對應 3 個字母的數字個數，n 是輸入中對應 4 個字母的數字個數，m+n 是輸入數字的總個數。除了返回值以外，空間復雜度主要取決于哈希表以及回溯過程中的遞歸調用層數，哈希表的大小與輸入無關，可以看成常數，遞歸調用層數最大為 m+n

源自力扣官方題解