【LeetCode Python实现】17. 电话号码的字母组合（中等）
2022-04-18 11:00:40

---

题目描述

给定一个仅包含数字 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'] 的一个数字。

参考代码

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        
        num_map = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        def dfs(idx, temp):
            if idx == len(digits):
                ret.append(temp)
            else:
                digit = digits[idx]
                for c in num_map[digit]:
                    temp += c
                    dfs(idx + 1, temp)
                    # 移除计算过的数
                    temp = temp[:-1]

        temp = ""
        ret = []
        dfs(0, temp)
        return ret