LeetCode - 17 电话号码的字母组合

你的名字 2023-09-26 11:15 87阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[17. 电话号码的字母组合 - 力扣（LeetCode）][17. _ - _LeetCode]

### 题目描述 ###

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

![f02cea16f958999ebf4b42bd49db6f27.png][]

### 示例 ###

> 输入：digits = "23"  
> 输出：\["ad","ae","af","bd","be","bf","cd","ce","cf"\]

> 输入：digits = ""  
> 输出：\[\]

> 输入：digits = "2"  
> 输出：\["a","b","c"\]

### 提示 ###

*  `0 <= digits.length <= 4`
 *  `digits[i]` 是范围 `['2', '9']` 的一个数字。

### 题目解析 ###

这道题和数组全排列的区别在于，数组全排列的每一层数据都是在同一个数组中捞取数据，因此需要一个额外的used数组，来记录数组元素的使用情况。

而本题，每一层数据取自不同数组，比如输入23，则第一层固定取2对应的字母数组\['a','b','c'\]中数据，第二层固定取3对应的字母数组\["d", "e", "f"\]中的数据。因此不需要额外的used来记录。

递归层级就是输入23的字符串长度2。

### JS算法源码 ###

### Python算法源码 ###

letters = [None, None, "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    
    class Solution(object):
        def letterCombinations(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
    
            if digits == "":
                return []
    
            res = []
            self.dfs(digits, 0, [], res)
            return res
            
        def dfs(self, digits, level, path, res):
            if level == len(digits):
                res.append("".join(path))
                return
            
            for c in letters[int(digits[level])]:
                path.append(c)
                self.dfs(digits, level + 1, path, res)
                path.pop()

[17. _ - _LeetCode]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
[f02cea16f958999ebf4b42bd49db6f27.png]: https://img-blog.csdnimg.cn/img_convert/f02cea16f958999ebf4b42bd49db6f27.png