17. 电话号码的字母组合

题目链接：17. 电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

核心思考：回溯法（DFS 枚举）

这道题需要生成所有可能的字母组合，是一道典型的排列组合枚举问题，适合用回溯法（Backtracking）来解决。

每个数字对应若干个字母，我们需要从左到右依次处理输入字符串 digits 中的每一个数字，并在该数字对应的所有字母中逐一尝试，然后递归处理下一个数字位。

具体流程如下：

1. 建立映射表：用一个数组 values 将数字 0-9 分别映射到其对应的字母字符串上。其中 0 和 1 不对应任何字母，为空字符串。
2. 递归枚举：定义递归函数 dfs(i)，表示当前正在处理第 i 个数字。对于 digits[i] 对应的每一个字母，将其填入路径数组 path[i] 中，然后递归调用 dfs(i + 1) 处理下一位。
3. 收集结果：当 i == n（即所有数字都处理完毕）时，将当前路径 path 拼接成字符串，加入结果列表 ans 中，然后返回上一层继续尝试其他字母。

值得注意的是，这里使用了一个固定长度的 path 数组而不是动态拼接字符串，避免了每次递归都创建新字符串对象的开销。

解题思路 (Python)

values = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        n = len(digits)
        if n == 0:
            return []
        
        ans = []
        path =  [""]*n

        def dfs(i):
            if i == n:
                ans.append("".join(path))
                return
            else:
                for char in values[int(digits[i])]:
                    path[i] = char
                    dfs(i+1)
        
        dfs(0)
        return ans

复杂度分析

• 时间复杂度：$O(3^m \times 4^n)$，其中 $m$ 是输入中对应 3 个字母的数字个数（如 2、3、4 等），$n$ 是对应 4 个字母的数字个数（如 7、9）。每个数字对应的字母都需要逐一枚举，最终生成的组合总数即为各位字母数量的乘积。
• 空间复杂度：$O(m + n)$，即输入字符串的长度。递归调用栈的深度等于 digits 的长度，path 数组的长度也与之相同。不计入存储结果的空间。