力扣刷题笔记：17.电话号码的字母组合（回溯模板题，直接套模板，另外列出动态规划的写法供大家参考）

￡神魔★判官ぃ 2022-11-06 08:55 112阅读 0赞

## 题目： ##

17、电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。  
![在这里插入图片描述][20210308210607716.png]

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

> **因为是模板题，思路比较简单，就不再赘述了，直接上代码。**

## 题解python代码： ##

**方法一：回溯**

直接套回溯模板：[https://blog.csdn.net/weixin\_44414948/article/details/114489545][https_blog.csdn.net_weixin_44414948_article_details_114489545]

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 = []
            path = []
    
            def backtrack(index):
                if index==len(digits):
                    res.append("".join(path))
                    return
                digit = digits[index]
                for ch in phoneMap[digit]:
                    path.append(ch)
                    backtrack(index+1)
                    path.pop()
            
            backtrack(0)
            return res

**方法二：动态规划**

动态方程为：dp\[i\] = \[x+y for x in dp\[i-1\] for y in dict\[digits\[i\]\]\]

class Solution:
        def letterCombinations(self, digits: str) -> List[str]:
            dict = {
        "2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
            if not digits:
                return []
            n = len(digits)
            dp = [[] for _ in range(n)]
            dp[0] = [letter for letter in dict[digits[0]]]
            for i in range(1,n):
                dp[i] = [x+y for x in dp[i-1] for y in dict[digits[i]]]
            return dp[-1]

本题两种算法时间复杂度相当。

> 作者：a-qing-ge  
> 链接：[https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/hui-su-dong-tai-gui-hua-liang-chong-jie-qzc3v/][https_leetcode-cn.com_problems_letter-combinations-of-a-phone-number_solution_hui-su-dong-tai-gui-hua-liang-chong-jie-qzc3v]  
> 来源：力扣（LeetCode）[https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/][https_leetcode-cn.com_problems_letter-combinations-of-a-phone-number]

[20210308210607716.png]: /images/20221023/f483028712bb406db45d6cce37759b12.png
[https_blog.csdn.net_weixin_44414948_article_details_114489545]: https://blog.csdn.net/weixin_44414948/article/details/114489545
[https_leetcode-cn.com_problems_letter-combinations-of-a-phone-number_solution_hui-su-dong-tai-gui-hua-liang-chong-jie-qzc3v]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/hui-su-dong-tai-gui-hua-liang-chong-jie-qzc3v/
[https_leetcode-cn.com_problems_letter-combinations-of-a-phone-number]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/