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

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

题目描述

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

题意分析

输入是一串只含 2 到 9 的数字，按九宫格键盘的规则每个数字对应一组字母，要求输出所有能拼出来的字母串，顺序不限。

约束里有三个关键信号。第一，输入长度不超过 4，说明结果规模最大是 $4^4 = 256$ 条，可以放心地把答案全部枚举出来，不存在剪枝需求。第二，输入位与输出位是一一对应的，第 k 个数字决定结果串的第 k 个字符，长度必然等于输入长度。第三，不同数字对应的字母集合互不相交，所以不会出现重复的结果串，不需要额外去重。

边界只有一个但很容易踩：输入可能是空串。空串意味着一个字母都没得选，题目要求返回空列表 []，而不是含一个空字符串的 [""]。这两者在判等时是不同的，必须在入口处特判。数字 1 和 0 不会出现在输入里，映射表里占位即可。

解法：回溯逐位选择字母

核心思路

问题关键：第 i 个数字决定结果的第 i 个字母，每一位都要从自己的候选集合中选一个。输入长度可变，不能写死多重循环，适合用回溯逐层枚举。

状态与选择：index 表示当前处理到第几个数字，path 保存已经选好的前缀。当前层只遍历 digits[index] 对应的字母；选一个字母后递归到下一层，返回时撤销这次选择。

不变量：进入 backtrack(index) 时，path 恰好对应 digits[0..index-1]，且长度为 index；函数返回时，path 恢复到进入前的状态。因此不同分支互不污染，也不需要 used 数组——各层候选集合由数字位置天然隔开。

正确性：递归每层为一个输入位枚举全部合法字母；到达末尾时，路径包含每一位的一次合法选择。任意组合对应递归树中的唯一一条根到叶路径，所以答案不重不漏。

解题步骤

  1. 空字符串直接返回空列表，避免把空路径误收为一个答案。
  2. 用数组保存 2 到 9 的字母映射，从 index = 0、空路径开始回溯。
  3. 若 index == digits.length()，说明每一位都已选择，将当前路径的快照加入结果。
  4. 否则遍历当前数字对应的字母：追加字母、递归 index + 1、删除末尾字母。

口述样例：digits = "23" 时，第一层依次选 a、b、c，每个前缀在第二层再选 d、e、f，得到 ad、ae、af、bd、be、bf、cd、ce、cf。

边界检查：digits = "" 返回 []；digits = "7" 返回 4 个组合；digits = "79" 应有 $4 \times 4 = 16$ 个组合，可检查 7、9 的四字母映射是否写全。

代码实现

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 位对应 3 个字母、b 位对应 4 个字母，长度 $d=a+b$，结果数 $R=3^a4^b$。

  • 时间复杂度：$O(Rd)$。共生成 $R$ 个结果，每次把长度为 $d$ 的路径复制成字符串。
  • 空间复杂度：$O(d)$，递归栈和路径最长均为 $d$；若计入输出，则为 $O(Rd)$。

关键点总结

  • 回溯骨架是「做选择—递归—撤销选择」，撤销保证兄弟分支共用同一条干净路径。
  • 每层候选由当前位置唯一决定，不存在元素复用冲突，因此不需要 used。
  • 收集答案时要复制路径；Java 的 StringBuilder 和 Go 的字节切片都会继续变化。
  • 面试时先说结果规模本身就是指数级，再说明算法已做到与输出规模同阶，无法通过剪枝减少必须返回的答案。

易错点总结

  • 空输入未特判：递归会把空路径收集成 [""]，而题目要求 []。
  • 递归后忘记删除末尾字符："23" 的兄弟分支会继承旧字符，生成长度错误的结果。
  • 到达叶子后忘记 return：继续访问 digits[index] 会越界。
  • 7 写成 "pqr" 或 9 写成 "wxy"："79" 会从 16 个答案缩水为 9 个。
  • 递归参数写成 ++index：修改了当前层状态，后续候选会跳层；应传 index + 1。

相似题目

题目 难度 考察点
22. 括号生成 中等 候选只有两种但需按左右括号计数剪枝，非法分支要提前掐断
39. 组合总和 中等 同一元素可重复选取，靠起始下标而非层号约束避免重复组合
46. 全排列 中等 各层共用同一候选池，必须引入 used 标记防止元素被选两次
77. 组合 中等 结果长度固定为 k，可用剩余元素数量做可行性剪枝
78. 子集 中等 每个元素只有选与不选两种分支，且每个节点都要收集答案
93. 复原 IP 地址 中等 每层切分长度不定，需校验数值范围与前导零
131. 分割回文串 中等 分支合法性依赖回文判定，通常配合预处理表加速
784. 字母大小写全排列 中等 数字位没有分支、字母位才分叉，层与层的候选数不等