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

约 6 分钟
文章信息 20 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 20-50 LeetCode 75 LeetCode 热题 100 面试经典 150 题 腾讯 字节 华为 微软 美团 拼多多 小米 百度 快手 滴滴 B站 猿辅导
标签
字符串 哈希表 回溯

题目描述

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

image-20260928204021466

image-20260928204021467

题意分析

输入一个只含数字 2 到 9 的字符串，每一位数字对应电话按键上的一组字母。必须按数字的原顺序，为每个位置选一个对应字母，返回全部可能的字符串，结果顺序不限。

每个结果的长度与数字串相同；重复数字的不同位置独立选择，字母也可以重复使用。数字 7、9 各对应四个字母，其余对应三个。现有实现也保留空输入返回空列表的处理。

解法：回溯逐位选择字母

核心思路

[!blue]

每个数字位置提供一组候选字母，完整结果就是每组各取一个。按位置递归即可：进入 backtrack(index) 时，路径长度恰好为 index，前面的字母已经分别对应数字串的前 index 个位置；当前层只枚举当前数字的映射字母。

选定一个字母后把它追加到路径，递归处理下一个位置。返回后删掉刚添加的末尾字母，再尝试本位置的其他候选。这样兄弟分支共享路径容器，却不会继承彼此的选择。

当 index 等于数字串长度时，所有位置都已选好，把当前路径转成独立字符串保存。Java 的 StringBuilder 和 Go 的字节切片随后还会修改，因此答案保存的是字符串快照。

每个答案唯一对应一串逐位选择，所有候选都会被枚举，不需要额外去重。字母是否在其他位置用过也不影响当前选择，所以不需要 used 数组。若输入为空，应在递归前直接返回，避免把没有字母的路径当作一个组合。

解题步骤

  1. 空输入直接返回空列表；为数字下标准备完整字母映射。
  2. 从 index = 0 和空路径开始回溯。
  3. index 到达数字串长度时，将路径复制成字符串加入结果，然后返回。
  4. 否则读取当前数字对应的字母组，逐个执行“追加字母、递归下一位、删除末尾字母”。
  5. 全部候选遍历完后，返回收集到的组合列表。

代码实现

class Solution {
    private static final String[] LETTERS = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();

        if (digits.length() == 0) {
            return res;
        }

        backtrack(digits, 0, new StringBuilder(), res);

        return res;
    }

    private void backtrack(String digits, int index, StringBuilder path, List<String> res) {
        if (index == digits.length()) {
            res.add(path.toString());

            return;
        }

        String letters = LETTERS[digits.charAt(index) - '0'];

        for (int i = 0; i < letters.length(); i++) {
            path.append(letters.charAt(i));
            backtrack(digits, index + 1, path, res);
            // 撤销当前数字选择的字母，再尝试同一数字的其他候选。
            path.deleteCharAt(path.length() - 1);
        }
    }
}

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }

    letters := []string{
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    }
    res := make([]string, 0)
    path := make([]byte, 0, len(digits))

    var backtrack func(int)
    backtrack = func(index int) {
        if index == len(digits) {
            res = append(res, string(path))
            return
        }

        choices := letters[digits[index]-'0']
        for i := 0; i < len(choices); i++ {
            path = append(path, choices[i])
            backtrack(index + 1)
            // 撤销当前数字选择的字母，再尝试同一数字的其他候选。
            path = path[:len(path)-1]
        }
    }

    backtrack(0)
    return res
}

复杂度分析

设非空输入中有 a 位对应三个字母、b 位对应四个字母，长度为 $d=a+b$，结果数为 $R=3^a4^b$。

  • 时间复杂度：$O(Rd)$，搜索生成 R 个结果，每个结果需要把长度为 d 的路径复制成字符串。
  • 空间复杂度：不计输出为 $O(d)$，路径和递归栈长度均不超过 d；全部结果占 $O(Rd)$。空输入直接返回，耗时和辅助空间为常数。

关键点总结

[!green]

  • 一层对应一个数字位置，路径长度与递归下标始终一致。
  • 候选由当前位置独立决定，重复数字或重复字母无需排除。
  • 撤销只删除当前层加入的最后一个字母，恢复兄弟分支的共同前缀。
  • 复杂度必须计入生成所有结果和复制字符串的成本。

易错点总结

[!yellow]

  • 空输入直接进入叶子收集，会得到含一个空串的列表，与现有空输入约定不同。
  • 返回上层后没有删除末尾字母，后续分支会继承旧选择，路径长度不再对应下标。
  • 保存路径后不立即返回，继续读取已越界的数字位置。
  • 将 7、9 的映射误写成三个字母，会系统性漏掉包含最后一个候选的组合。
  • 递归调用传入 ++index，同时改变本层状态，后续候选会跳过位置；应传 index + 1。
  • 用全局使用标记阻止字母重复，添加了题目没有要求的限制。

相似题目

题目 难度 关联与区别
补充题 136. 多组键值选项的笛卡尔积 中等 每个数字对应一组选项，完整答案就是每组选一个字符的笛卡尔积。
22. 括号生成 中等 同样按位置回溯构造字符串，括号题还需要维护前缀合法性，本题各位置选择独立。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/78578419
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！