LeetCode 第 17 题：“电话号码的字母组合”

字数 1560 2025-10-26 02:46:34

好的，我们来看 LeetCode 第 17 题：“电话号码的字母组合”。

题目描述

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

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

数字到字母的映射：

2: "abc"
3: "def"
4: "ghi"
5: "jkl"
6: "mno"
7: "pqrs"
8: "tuv"
9: "wxyz"

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

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]

解题思路：循序渐进

这个问题本质上是要求出所有可能的组合，非常适合用 回溯算法（深度优先搜索） 来解决。

第一步：问题分析

每个数字对应几个字母。
我们需要从每个数字对应的字母中选取一个，然后与下一个数字对应的字母进行组合。
例如输入 "23"：
- 第一个数字 2 对应 "abc"。
- 第二个数字 3 对应 "def"。
- 我们需要生成 "a" 和 "d","e","f" 组合，"b" 和 "d","e","f" 组合，等等。

第二步：确定算法框架

我们可以把这个问题看作一棵树：

根节点是空字符串。
第一层是第一个数字对应的所有字母。
第二层是在第一层的基础上，加上第二个数字对应的所有字母。
以此类推，直到处理完所有数字。

回溯算法的核心思想：

选择一个路径（选择一个字母）。
进入下一层决策树（处理下一个数字）。
撤销选择（回溯），尝试其他可能性。

第三步：定义递归函数

我们需要一个递归函数，参数通常包括：

当前构建的组合字符串 current。
当前处理到的数字索引 index。

递归过程：

如果 index 等于数字字符串的长度，说明已经处理完所有数字，将 current 加入结果列表。
否则，获取当前数字对应的字母串。
遍历这个字母串中的每个字母：
- 将字母加入 current。
- 递归调用函数处理下一个数字（index + 1）。
- 回溯：将刚才加入的字母从 current 中移除，尝试下一个字母。

第四步：代码实现细节

使用一个列表 result 存储最终结果。
使用一个字典存储数字到字母的映射。
注意处理空字符串输入的特殊情况。

第五步：举例说明

以 digits = "23" 为例：

初始调用：index = 0, current = ""。
数字 2 对应 "abc"。
- 取 'a'，current = "a"，递归处理 index = 1。
  - 数字 3 对应 "def"。
    - 取 'd'，current = "ad"，index = 2，加入结果。
    - 回溯，current = "a"，取 'e'，current = "ae"，加入结果。
    - 回溯，取 'f'，current = "af"，加入结果。
- 回溯到 index = 0，current = ""，取 'b'，重复上述过程生成 "bd","be","bf"。
- 再取 'c'，生成 "cd","ce","cf"。
最终结果：["ad","ae","af","bd","be","bf","cd","ce","cf"]。

总结

这道题是回溯算法的经典入门题，它帮助我们理解如何通过递归和回溯来枚举所有可能的组合。关键点在于：

将问题转化为树形结构。
递归遍历所有分支。
在递归返回时进行回溯，确保每个分支互不干扰。

通过这种方式，我们可以系统地生成所有解，而不会遗漏任何可能性。

好的，我们来看 LeetCode 第 17 题：“电话号码的字母组合” 。题目描述给定一个仅包含数字 2 到 9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。数字到字母的映射与电话按键相同（如下所示）。注意，数字 1 不对应任何字母。数字到字母的映射：示例 1：输入：digits = "23" 输出：[ "ad","ae","af","bd","be","bf","cd","ce","cf" ] 示例 2：输入：digits = "" 输出：[ ] 示例 3：输入：digits = "2" 输出：[ "a","b","c" ] 解题思路：循序渐进这个问题本质上是要求出所有可能的组合，非常适合用回溯算法（深度优先搜索）来解决。第一步：问题分析每个数字对应几个字母。我们需要从每个数字对应的字母中选取一个，然后与下一个数字对应的字母进行组合。例如输入 "23" ：第一个数字 2 对应 "abc" 。第二个数字 3 对应 "def" 。我们需要生成 "a" 和 "d","e","f" 组合， "b" 和 "d","e","f" 组合，等等。第二步：确定算法框架我们可以把这个问题看作一棵树：根节点是空字符串。第一层是第一个数字对应的所有字母。第二层是在第一层的基础上，加上第二个数字对应的所有字母。以此类推，直到处理完所有数字。回溯算法的核心思想：选择一个路径（选择一个字母）。进入下一层决策树（处理下一个数字）。撤销选择（回溯），尝试其他可能性。第三步：定义递归函数我们需要一个递归函数，参数通常包括：当前构建的组合字符串 current 。当前处理到的数字索引 index 。递归过程：如果 index 等于数字字符串的长度，说明已经处理完所有数字，将 current 加入结果列表。否则，获取当前数字对应的字母串。遍历这个字母串中的每个字母：将字母加入 current 。递归调用函数处理下一个数字（ index + 1 ）。回溯：将刚才加入的字母从 current 中移除，尝试下一个字母。第四步：代码实现细节使用一个列表 result 存储最终结果。使用一个字典存储数字到字母的映射。注意处理空字符串输入的特殊情况。第五步：举例说明以 digits = "23" 为例：初始调用： index = 0 , current = "" 。数字 2 对应 "abc" 。取 'a' ， current = "a" ，递归处理 index = 1 。数字 3 对应 "def" 。取 'd' ， current = "ad" ， index = 2 ，加入结果。回溯， current = "a" ，取 'e' ， current = "ae" ，加入结果。回溯，取 'f' ， current = "af" ，加入结果。回溯到 index = 0 ， current = "" ，取 'b' ，重复上述过程生成 "bd","be","bf" 。再取 'c' ，生成 "cd","ce","cf" 。最终结果： ["ad","ae","af","bd","be","bf","cd","ce","cf"] 。总结这道题是回溯算法的经典入门题，它帮助我们理解如何通过递归和回溯来枚举所有可能的组合。关键点在于：将问题转化为树形结构。递归遍历所有分支。在递归返回时进行回溯，确保每个分支互不干扰。通过这种方式，我们可以系统地生成所有解，而不会遗漏任何可能性。