LC 17电话号码的字母组合Letter Combinations of a Phone Number　中等

给定仅含 2-9 的数字串，按手机九键的字母映射，返回它可能表示的全部字母组合。

思路 建 数字→字母 映射，回溯逐位选一个字母，递归到末尾拼接收集；空串直接返回 []。

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

        def dfs(i):
            if i == len(digits):
                ans.append("".join(path))
                return
            for ch in d[digits[i]]:
                path.append(ch)
                dfs(i + 1)
                path.pop()

        dfs(0)
        return ans