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

Categories:

题目描述
思路分析
1. 解法一：回溯（推荐）
相似题目

题目描述

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

思路分析

解法一：回溯（推荐）

核心思路：

建立数字到字母的映射表（phoneMap），每个数字对应 3~4 个字母。

n 位数字构成一棵 n 层多叉树，每层的分支数等于当前数字对应的字母数。

backtrack(index) 表示正在填第 index 位字母：

终止条件：index == len(digits) 时，path 已构成完整组合，加入结果集。

递归选择：枚举 phoneMap[digits[index]] 中每个字母 c，将 c 追加到 path，递归处理下一位，返回后弹出 c（回溯）。

由于每层只能选当前数字对应的字母，层与层之间字母集合天然不同，无需 used[] 标记，也无需 start 参数控制起始位置。

复杂度分析：

时间复杂度：O(3^m × 4^n × (m+n))，其中 m 表示对应 3 个字母的数字个数，n 表示对应 4 个字母的数字个数，每个组合需 O(m+n) 时间构造字符串。

空间复杂度：O(m+n)，其中 m+n 为输入数字总长度，递归栈深度与 path 长度均为 O(m+n)。

class Solution {

    // 数字到字母的映射，下标即数字字符对应的整数值
    private static final String[] PHONE_MAP = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    private List<String> res = new ArrayList<>();
    private StringBuilder path = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) {
            return res;
        }
        backtrack(digits, 0);
        return res;
    }

    private void backtrack(String digits, int index) {
        // 已处理完所有数字，path 即为一个完整组合
        if (index == digits.length()) {
            res.add(path.toString());
            return;
        }
        // 枚举当前数字对应的每个字母
        String letters = PHONE_MAP[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            // 选择字母 c，加入路径
            path.append(c);
            backtrack(digits, index + 1);
            // 回溯：撤销选择
            path.deleteCharAt(path.length() - 1);
        }
    }
}

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

    // 数字到字母的映射
    phoneMap := map[byte]string{
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
    }

    var res []string
    var path []byte

    var backtrack func(index int)
    backtrack = func(index int) {
        // 已处理完所有数字，path 即为一个完整组合
        if index == len(digits) {
            res = append(res, string(path))
            return
        }
        // 枚举当前数字对应的每个字母
        for _, c := range phoneMap[digits[index]] {
            // 选择字母 c，加入路径
            path = append(path, byte(c))
            backtrack(index + 1)
            // 回溯：撤销选择
            path = path[:len(path)-1]
        }
    }

    backtrack(0)
    return res
}

相似题目

题目	难度	考察点
39. 组合总和	中等	回溯
22. 括号生成	中等	回溯
46. 全排列	中等	回溯
78. 子集	中等	回溯枚举
93. 复原 IP 地址	中等	回溯 + 剪枝
131. 分割回文串	中等	回溯 + 动态规划
40. 组合总和 II	中等	回溯 + 去重

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/78578419