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

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

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

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

示例 2:
输入：digits = ""
输出：[]

示例 3:
输入：digits = "2"
输出：["a","b","c"]

解题思路

输入： 给定一个包含 2-9 的字符串

输出： 返回它能表示的所有字母组合

本题属于基本回溯问题。

• 用一个数组 MAPPING 映射数字到字母。
• 使用回溯（DFS）来“穷举每个数字对应的所有字母组合”。
• 每次递归处理一位数字，并尝试它对应的所有可能字母。
• 使用 path 记录当前选择的路径（组合）。
• 当走到最后一个数字时，将当前组合加入结果列表 ans 中。

回溯三问

1. 当前操作？

   • 在当前位置 i，尝试选择 digits[i] 所映射的一个字母 c 放入 path[i]。
   • 也就是把数字 digits[i] 上的一个字母放到路径上，表示“我选择了这个字母”。

2. 子问题？

   • 选择了 digits[i] 上的字母 c 之后，需要继续递归处理 下一个数字 digits[i+1] 的所有字母。
   • 也就是在 digits[i+1] 继续选择。

3. 下一个子问题？

   • 下一步递归就是 dfs(i+1)，表示在下一个数字位置继续构造路径，直到整个路径被填满。

剪枝条件

• 由于每个数字（2-9）都有映射的字母，因此这题其实不需要额外剪枝。
• 如果 digits 为空（n==0），直接返回空结果即可。

代码实现

python

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 数字到字母的映射（2~9）
        MAPPING = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        n = len(digits)

        # 如果输入为空，返回空列表
        if not n:
            return []

        ans = []            # 存储所有可能的结果
        path = [''] * n     # 临时路径，长度等于输入 digits 的长度

        # 回溯函数：从第 i 位开始递归构造
        def dfs(i):
            # 如果已经填满整个 path，构造出一个完整组合
            if i == n:
                ans.append(''.join(path))  # 把 path 转换成字符串加入答案
                return

            # 遍历当前 digits[i] 对应的所有字母
            for c in MAPPING[int(digits[i])]:
                path[i] = c        # 选择当前字母放入路径
                dfs(i + 1)         # 递归处理下一位

        dfs(0)     # 从第 0 位开始回溯
        return ans

javascript

const letterCombinations = function(digits) {
    // 数字到字母的映射（对应手机按键）
    const MAPPING = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];

    // 如果输入为空字符串，直接返回空数组
    if (!digits) return [];

    const ans = []; // 用于存储所有合法的字母组合
    const n = digits.length; // 输入数字的长度
    const path = Array(digits.length).fill(0); // 临时路径数组，记录当前组合

    // 回溯函数，i 表示当前处理第 i 个数字
    function dfs(i) {
        // 如果已经处理完所有数字，构造出一个完整组合
        if (i == n) {
            ans.push(path.join('')); // 把路径拼成字符串加入结果数组
            return;
        }

        // 遍历当前 digits[i] 对应的所有字母
        for (let c of MAPPING[digits[i]]) {
            path[i] = c;    // 选择当前字母放入第 i 位
            dfs(i + 1);     // 递归处理下一个数字
        }
    }

    dfs(0); // 从第 0 个数字开始回溯
    return ans;
};

复杂度分析

时间复杂度：O(4^n * n)

• 4^n 是所有可能的组合数
• n 是每次组合字符串的复制成本

空间复杂度：O(n)

链接

17 国际版

17 中文版