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

题目

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

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

方法：递归、回溯

• 判断字符串是否为空
• 按照数字到字母的映射定义一个字典，数字部分为键 key，字母部分为值 value。result 表示所有符合要求的字符串，path 表示当前将要组成字符串的字母（们），index 表示字符串 digits 的索引

backtrack 部分：

• 当 path 的长度等于字符串 digits 的长度时，表示此时 path 中存储的字母个数已等于要求的字母个数，则将 path 中的字母组合成字符串，加入 result 中
• 当 path 的长度不等于字符串 digits 的长度时，表示存在数字对应的字母未加入 path。num 表示此时该从字符串 digits 中获取的数字，使用键 num 查找字典中相应的字母字符串，通过循环实现 path 的建立

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        dict = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        result = []
        path = []
        
        def backtrack(index):
            if len(path) == len(digits):
                result.append("".join(path))
                return None 
            num = digits[index]
            for letter in dict[num]:
                path.append(letter)
                backtrack(index + 1)
                path.pop()
        
        backtrack(0)
        return result

参考

代码相关：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/