17 电话号码的字母组合

一、题目

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

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

487

二、题解

思路：回溯 / DFS

1. 核心思路

这道题本质上是一个组合问题。

每一个数字都对应多个字母，我们需要从每个数字对应的字母中选择一个，最终拼成一个完整字符串。

例如：

digits = "23"

2 -> abc
3 -> def

可以理解为：

先从 a、b、c 中选一个
再从 d、e、f 中选一个

所以可以使用回溯来枚举所有可能情况。

2. 具体步骤

  1. 建立数字到字母的映射关系。
  2. 从 digits 的第 0 个数字开始处理。
  3. 每次取出当前数字对应的所有字母。
  4. 依次选择其中一个字母加入当前路径。
  5. 递归处理下一个数字。
  6. 当路径长度等于 digits.length() 时，说明得到一个完整组合，加入结果集。
  7. 回溯时撤销刚才选择的字母，继续尝试其他可能。

3. 关键逻辑

  • index 表示当前处理到 digits 的第几个数字。
  • path 表示当前已经拼接出来的字符串。
  • 如果 index == digits.length()，说明已经处理完所有数字，可以加入答案。
  • 每次递归前执行 path.append(...)，表示选择当前字母。
  • 每次递归后执行 path.deleteCharAt(...)，表示撤销选择，回到上一层继续尝试。

例如：

digits = "23"

选择 a
    选择 d -> ad
    选择 e -> ae
    选择 f -> af

选择 b
    选择 d -> bd
    选择 e -> be
    选择 f -> bf

选择 c
    选择 d -> cd
    选择 e -> ce
    选择 f -> cf

最终结果：

["ad","ae","af","bd","be","bf","cd","ce","cf"]

三、代码

import java.util.*;

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        // 1. 处理特殊情况
        if (digits == null || digits.length() == 0) {
            return result;
        }

        // 2. 定义数字到字母的映射
        String[] map = new String[]{
            "",     // 0
            "",     // 1
            "abc",  // 2
            "def",  // 3
            "ghi",  // 4
            "jkl",  // 5
            "mno",  // 6
            "pqrs", // 7
            "tuv",  // 8
            "wxyz"  // 9
        };

        // 3. 定义当前路径
        StringBuilder path = new StringBuilder();

        // 4. 开始回溯
        backtrack(digits, 0, map, path, result);

        // 5. 返回结果
        return result;
    }

    /**
     * 回溯函数
     *
     * @param digits 原始数字字符串
     * @param index 当前处理到 digits 的第几个位置
     * @param map 数字到字母的映射
     * @param path 当前已经拼接出的字符串
     * @param result 最终结果集
     */
    private void backtrack(String digits, int index, String[] map,
                           StringBuilder path, List<String> result) {
        // 如果已经处理完所有数字，说明得到一个完整组合
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }

        // 获取当前数字字符
        char digitChar = digits.charAt(index);

        // 将字符数字转成真正的数字
        int digit = digitChar - '0';

        // 获取当前数字对应的字母
        String letters = map[digit];

        // 遍历当前数字对应的所有字母
        for (int i = 0; i < letters.length(); i++) {
            // 选择当前字母
            path.append(letters.charAt(i));

            // 递归处理下一个数字
            backtrack(digits, index + 1, map, path, result);

            // 撤销选择，回到上一层
            path.deleteCharAt(path.length() - 1);
        }
    }
}

四、复杂度分析

时间复杂度：O(4n×n)O(4^n \times n)

说明：

n 是 digits 的长度。

每个数字最多对应 4 个字母，例如 7 -> pqrs，9 -> wxyz。

所以最多会产生 4n4^n 个组合。

每次把 StringBuilder 转成字符串时，需要 O(n)O(n) 的时间，因此总时间复杂度是：

O(4^n * n)

空间复杂度：O(n)O(n)

说明：

递归深度最多为 n，StringBuilder 中最多存放 n 个字符。

如果不计算返回结果数组，空间复杂度是：

O(n)

如果计算返回结果数组，最多有 4n4^n 个字符串，每个字符串长度为 n，空间复杂度是：

O(4^n * n)

评论