（LeetCodeHot100）17. 电话号码的字母组合——letter-combinations-of-a-phone-number

zhangzhang2025-11-292025-12-03

17. 电话号码的字母组合——letter-combinations-of-a-phone-number

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

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

示例 1：

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

示例 2：

1 2	输入：digits = "2" 输出：["a","b","c"]

提示：

1 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

方法一：回溯

首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。

回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。

回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

代码解释：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    /**
     * 题目：电话号码的字母组合（LeetCode 17）
     * 功能：给定包含数字 2-9 的字符串，返回所有可能的字母组合（映射规则同手机九宫格键盘）
     * @param digits 输入的数字字符串（仅包含2-9）
     * @return 所有可能的字母组合列表
     */
    public List<String> letterCombinations(String digits) {
        // 存储最终结果的列表（所有字母组合）
        List<String> combinations = new ArrayList<String>();
        
        // 边界条件：如果输入字符串为空，直接返回空列表（无组合可生成）
        if (digits.length() == 0) {
            return combinations;
        }
        
        // 手机九宫格数字到字母的映射表（匿名内部类+实例初始化块，创建即填充数据）
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");  // 数字2对应字母a、b、c
            put('3', "def");  // 数字3对应字母d、e、f
            put('4', "ghi");  // 数字4对应字母g、h、i
            put('5', "jkl");  // 数字5对应字母j、k、l
            put('6', "mno");  // 数字6对应字母m、n、o
            put('7', "pqrs"); // 数字7对应字母p、q、r、s
            put('8', "tuv");  // 数字8对应字母t、u、v
            put('9', "wxyz"); // 数字9对应字母w、x、y、z
        }};
        
        // 调用回溯算法生成所有组合
        // 参数说明：结果列表、映射表、输入数字、当前处理的数字索引、当前拼接的字母组合（用StringBuffer高效修改）
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        
        return combinations;
    }

    /**
     * 回溯算法核心方法：递归生成所有字母组合
     * 思路：按数字索引逐步选择每个数字对应的字母，拼接成组合，直到处理完所有数字则加入结果
     * @param combinations 最终结果列表（存储所有有效组合）
     * @param phoneMap 数字-字母映射表
     * @param digits 输入的数字字符串
     * @param index 当前正在处理的数字在digits中的索引（从0开始，标记处理进度）
     * @param combination 当前正在拼接的字母组合（动态修改，避免重复创建字符串）
     */
    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        // 递归终止条件：当前索引等于数字字符串长度 → 已拼接完一组有效组合
        if (index == digits.length()) {
            // 将当前拼接的组合转为String，加入结果列表
            combinations.add(combination.toString());
        } else {
            // 1. 获取当前索引对应的数字字符（如digits="23"，index=0时获取'2'）
            char digit = digits.charAt(index);
            // 2. 从映射表中获取该数字对应的所有字母（如'2'对应"abc"）
            String letters = phoneMap.get(digit);
            // 3. 获取字母的长度（用于循环遍历每个可能的字母）
            int lettersCount = letters.length();
            
            // 循环遍历当前数字对应的所有字母，逐个尝试拼接
            for (int i = 0; i < lettersCount; i++) {
                // 拼接当前字母到组合中（StringBuffer append高效添加）
                combination.append(letters.charAt(i));
                // 递归处理下一个数字（索引+1，继续拼接后续字母）
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                // 回溯关键：删除最后拼接的字母，恢复到上一层状态，尝试下一个可能的字母
                // （如拼接"ad"后，删除'd'，再拼接"ae"）
                combination.deleteCharAt(index);
            }
        }
    }
}

如果没有 deleteCharAt(index)，会发生什么？

拼接 ad 后，combination 一直是 ad；
下一次循环会拼接 e → 变成 ade（这是错误的，因为 digits 只有 2 个数字，最多 2 个字母）；
最终会生成 ade、adf、bde... 等无效组合，而且无法回到上一层尝试其他首字母。

复杂度分析

时间复杂度：O(3m×4n)，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，不同的字母组合一共有 3m×4n 种，需要遍历每一种字母组合。
空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。