【LeetCode每日一题】——17.电话号码的字母组合

一【题目类别】

• 回溯

二【题目难度】

• 中等

三【题目编号】

• 17.电话号码的字母组合

四【题目描述】

• 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
• 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
  

五【题目示例】

• 示例 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'] 的一个数字。

七【解题思路】

• 但凡涉及到组合类的题目，基本都使用回溯算法解决，本题也不例外，不过是在原本的基础上添加映射关系
• 根据题目信息可知，我们最终组合的是字母，但是输入数据为数字，所以需要简历一个数字到字母的映射
• 其余步骤和正常的回溯过程一致
  • 设置边界条件：如果所有的数字都遍历完毕了，就完成此次计算
  • 回溯拼接某一电话号码对应的字母：和正常的回溯过程一致，不过需要先取出数字对应的字母进行回溯
• 最后返回结果即可
• 具体细节可以参考下面的代码

八【时间频度】

• 时间复杂度：$O(3^m\times 4^n)$，$m$为$3$个字母对应的数字个数，$n$为$4$个字母对应的数字个数
• 空间复杂度：$O(m+n)$，$m$为$3$个字母对应的数字个数，$n$为$4$个字母对应的数字个数

九【代码实现】

1. Java语言版

class Solution {// 数字和字母的映射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<>();}// 存储最终结果List<String> res = new ArrayList<>();// 从第一个电话号码开始计算dfs(res, new StringBuffer(), digits, 0);// 返回最终结算结果return res;}// 使用回溯计算电话号码的字母组合private void dfs(List<String> res, StringBuffer temp, String digits, int index) {// 将所有电话号码遍历完毕即可返回if (index == digits.length()) {res.add(temp.toString());return;}// 回溯拼接某一电话号码对应的字母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()# 数字和字母的映射phoneMap = {"2" : "abc","3" : "def","4" : "ghi","5" : "jkl","6" : "mno","7" : "pqrs","8" : "tuv","9" : "wxyz",}# 存储最终结果res = list()# 存储临时结果temp = list()# 使用回溯计算电话号码的字母组合def dfs(index):# 将所有电话号码遍历完毕即可返回if index == len(digits):res.append("".join(temp))return# 回溯拼接某一电话号码对应的字母digit = digits[index]for letter in phoneMap[digit]:temp.append(letter)dfs(index + 1)temp.pop()# 从第一个电话号码开始计算dfs(0)# 返回最终结算结果return res

3. C++语言版

class Solution {public:// 数字和字母的映射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;}// 回溯拼接某一电话号码对应的字母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) {// 存储最终结果vector<string> res;// 边界条件的判断if (digits.empty()) {return res;}// 存储临时结果string temp;// 从第一个电话号码开始计算dfs(res, temp, digits, 0);// 返回最终结算结果return res;}
};

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版