【LeetCode Python實(shí)現(xiàn)】17. 電話號(hào)碼的字母組合（中等）
2022-04-18 11:00:40

---

題目描述

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(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'] 的一個(gè)數(shù)字。

參考代碼

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)
                    # 移除計(jì)算過的數(shù)
                    temp = temp[:-1]

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