17. 电话号码的字母组合（中）

• 题目
• 题解：回溯

题目

题解：回溯

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:#检查输入的数字串 digits 是否为空
            return []
        a = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}#定义字典 a，其中键为数字字符，值为对应的字母字符串
        def backtrack(combination, next_digits):#combination 表示当前的字母组合，next_digits 表示剩余的数字串。
            if len(next_digits) == 0:#若剩余的数字串为空，说明已经生成了一个完整的组合，将其添加到结果列表 result 中。
                result.append(combination)  # 将当前组合添加到结果列表中
            else:#如果剩余的数字串不为空
                current_digit = next_digits[0]#取出剩余数字串的第一个数字
                letters = a[current_digit]  # 通过字典 a 获取当前数字对应的字母字符串
                for letter in letters:
                    combination += letter#将当前字母 letter 添加到当前组合 combination 中
                    backtrack(combination, next_digits[1:])#递归调用 backtrack 函数，传入更新后的参数 combination 和去掉第一个数字的剩余数字串 next_digits[1:]
                    combination = combination[:-1]  #撤销选择，回溯到上一层，恢复状态，去除最后一个字母
        result = []
        backtrack("", digits)  # 初始调用回溯函数，传入空字符串和输入的数字串
        return result