题解 | #牛名生成器#

• 题目考察的知识点 : 回溯
• 题目解答方法的文字分析：

1. 回溯法枚举所有可能的牛名组合。对于每个数字，找出它所对应的所有字母，并依次选取其中的一个字母，然后递归搜索下一个数字。在搜索过程中，需要记录已选取的字母和当前组合，以及未被处理的数字。当所有数字都被处理完毕时，将当前组合加入答案中。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param digits string字符串
# @return string字符串一维数组
#
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        mapping = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        res = []
        path = []

        def backtrack(start: int) -> None:
            if len(path) == len(digits):
                res.append("".join(path))
                return

            for i in range(start, len(digits)):
                for ch in mapping[digits[i]]:
                    path.append(ch)
                    backtrack(i + 1)
                    path.pop()

        backtrack(0)

        return res