一【題目類別】

• 回溯

二【題目難度】

• 中等

三【題目編號】

• 17.電話號碼的字母組合

四【題目描述】

• 給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。
• 給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。
  

五【題目示例】

• 示例 1：

  • 輸入：digits = “23”
  • 輸出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

• 示例 2：

  • 輸入：digits = “”
  • 輸出：[]

• 示例 3：

  • 輸入：digits = “2”
  • 輸出：[“a”,“b”,“c”]

六【題目提示】

• 0 <= digits.length <= 4
• digits[i] 是范圍 ['2', '9'] 的一個數(shù)字。

七【解題思路】

• 但凡涉及到組合類的題目，基本都使用回溯算法解決，本題也不例外，不過是在原本的基礎(chǔ)上添加映射關(guān)系
• 根據(jù)題目信息可知，我們最終組合的是字母，但是輸入數(shù)據(jù)為數(shù)字，所以需要簡歷一個數(shù)字到字母的映射
• 其余步驟和正常的回溯過程一致
  • 設(shè)置邊界條件：如果所有的數(shù)字都遍歷完畢了，就完成此次計算
  • 回溯拼接某一電話號碼對應(yīng)的字母：和正常的回溯過程一致，不過需要先取出數(shù)字對應(yīng)的字母進行回溯
• 最后返回結(jié)果即可
• 具體細節(jié)可以參考下面的代碼

八【時間頻度】

• 時間復雜度：$O(3^m\times 4^n)$，$m$為$3$個字母對應(yīng)的數(shù)字個數(shù)，$n$為$4$個字母對應(yīng)的數(shù)字個數(shù)
• 空間復雜度：$O(m+n)$，$m$為$3$個字母對應(yīng)的數(shù)字個數(shù)，$n$為$4$個字母對應(yīng)的數(shù)字個數(shù)

九【代碼實現(xiàn)】

1. Java語言版

class Solution {// 數(shù)字和字母的映射private static final String[] phoneMap = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz",};public List<String> letterCombinations(String digits) {// 邊界條件的判斷if (digits == null || digits.length() == 0) {return new ArrayList<>();}// 存儲最終結(jié)果List<String> res = new ArrayList<>();// 從第一個電話號碼開始計算dfs(res, new StringBuffer(), digits, 0);// 返回最終結(jié)算結(jié)果return res;}// 使用回溯計算電話號碼的字母組合private void dfs(List<String> res, StringBuffer temp, String digits, int index) {// 將所有電話號碼遍歷完畢即可返回if (index == digits.length()) {res.add(temp.toString());return;}// 回溯拼接某一電話號碼對應(yīng)的字母char digit = digits.charAt(index);String letters = phoneMap[digit - '0'];for (int i = 0; i < letters.length(); i++) {temp.append(letters.charAt(i));dfs(res, temp, digits, index + 1);temp.deleteCharAt(temp.length() - 1);}}}

2. Python語言版

class Solution:def letterCombinations(self, digits: str) -> List[str]:# 邊界條件的判斷if not digits:return list()# 數(shù)字和字母的映射phoneMap = {"2" : "abc","3" : "def","4" : "ghi","5" : "jkl","6" : "mno","7" : "pqrs","8" : "tuv","9" : "wxyz",}# 存儲最終結(jié)果res = list()# 存儲臨時結(jié)果temp = list()# 使用回溯計算電話號碼的字母組合def dfs(index):# 將所有電話號碼遍歷完畢即可返回if index == len(digits):res.append("".join(temp))return# 回溯拼接某一電話號碼對應(yīng)的字母digit = digits[index]for letter in phoneMap[digit]:temp.append(letter)dfs(index + 1)temp.pop()# 從第一個電話號碼開始計算dfs(0)# 返回最終結(jié)算結(jié)果return res

3. C++語言版

class Solution {public:// 數(shù)字和字母的映射const vector<string> phoneMap = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz",};// 使用回溯計算電話號碼的字母組合void dfs(vector<string>& res, string& temp, string digits, int index) {// 將所有電話號碼遍歷完畢即可返回if (index == digits.size()) {res.push_back(temp);return;}// 回溯拼接某一電話號碼對應(yīng)的字母int digit = digits[index] - '0';const string& letters = phoneMap[digit];for (char letter : letters) {temp.push_back(letter);dfs(res, temp, digits, index + 1);temp.pop_back();}}vector<string> letterCombinations(string digits) {// 存儲最終結(jié)果vector<string> res;// 邊界條件的判斷if (digits.empty()) {return res;}// 存儲臨時結(jié)果string temp;// 從第一個電話號碼開始計算dfs(res, temp, digits, 0);// 返回最終結(jié)算結(jié)果return res;}
};

十【提交結(jié)果】

1. Java語言版
   

2. Python語言版
   

3. C++語言版