LeetCode题解：17.电话号码的数字组合【Python题解超详细，回溯法、多叉树】，知识拓展：深度优先搜索与广度优先搜索
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
解答
class Solution(object):def letterCombinations(self, digits):""":type digits: str:rtype: List[str]"""# 思路一：回溯法# 对于digit为空的特殊情况，直接返回[]if not digits:return []# 定义数字与字母映射的字典phone_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl','6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}# 定义回溯函数# combination：当前已经生成的组合# nextdigits：剩余未处理的数字def backtract(combination,nextdigits):# 如果没有剩余数字，则读入combination并停止if len(nextdigits)==0:output.append(combination)return # 遍历当前数字对应的所有字母，进入下一阶段for letter in phone_map[nextdigits[0]]:# 将当前字母加入组合，并递归处理剩余数字backtract(combination+letter,nextdigits[1:])# 输出字典output=[]# 初始化回溯函数backtract("",digits)return output# # 思路二：构建多叉树# # 对于特殊情况，直接输出[]# if not digits:# return []# # 定义数字与字母映射的字典# phone_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl','6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}# # 定义深度优先搜索（DFS）函数# # node：当前数字对应的字母映射# # path：当前路径，即已生成的部分组合# def dfs(node,path):# # 如果路径长度等于输入数字长度，表示生成了一个完整组合# if len(path)==len(digits):# output.append(path)# return# # 如果当前节点为空，直接返回（无效分支）# if node is None:# return# # 遍历当前数字对应的所有字母# for letter in phone_map[node]:# dfs(digits[len(path) + 1] if len(path) + 1 < len(digits) else None,path+letter)# output=[]# dfs(digits[0],"")# return output
思路一，回溯法：其核心思想是逐步生成所有可能的字母组合，通过递归遍历当前数字对应的所有字母，并将当前字母加入到已经生成的部分组合中。当没有剩余数字时，将完整的组合加入结果列表。这种方法的优点是逻辑清晰，容易实现递归树的分支剪枝。
思路二，多叉树的深度优先搜索：通过构造一棵树，每个数字的字母映射为一层，路径上的节点代表当前生成的组合。通过递归从顶层到叶子节点（即完成一个完整组合）逐层搜索，并将完整的路径加入结果列表。这种方法本质上也是通过递归实现，但更侧重于以树的结构来思考问题。相比回溯法，逻辑上稍复杂，但仍能很好地生成所有组合。
对比两种方法，回溯法以 "递归 + 剪枝" 的方式，通过遍历每个数字的字母映射生成组合，逻辑简洁明了，易于实现；多叉树的 DFS则从树的结构出发，递归生成字母组合，逻辑上与回溯法类似，但代码中显示了树的层级关系，适合对树结构有直观理解的场景。并且，两种方法在时间复杂度上相同，均为 O(（)
n 为包含3个字母的数字数量，m 为包含4个字母的数字数量）。
知识拓展：深度优先搜索 vs. 广度优先搜索
深度优先搜索（Depth-First Search, DFS）
概念
深度优先搜索是一种搜索策略，它会沿着一个路径不断深入到树或图的叶子节点，直到不能再继续深入为止，然后回溯到上一个分支点继续探索其他路径。它优先关注的是路径的深度。
核心特点
- 深入探索：优先沿着路径一直深入到底。
- 回溯机制：在某路径不能继续深入时，回到上一个分支点继续探索。
- 使用栈结构：可以用递归（隐式栈）或显式栈实现。
A/ \B C/ \
D E# 其邻接表的结构如下：
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': [],'F': []
}
以图中的搜索为例，假设我们从节点 A 出发，目标是访问所有节点，则深度优先的访问顺序为：A → B → D → E → C，其搜索过程如下：
- 从
A出发，访问B。 - 从
B深入到D，访问D。 - 从
D回溯到B，然后访问E。 - 从
B回溯到A，然后访问C。
实现（递归版本）
def dfs(node, visited):if node in visited: # 如果节点已访问过，直接返回returnvisited.add(node) # 标记当前节点为已访问print(node) # 访问当前节点for neighbor in graph[node]: # 遍历临接表中的相邻节点dfs(neighbor, visited)
广度优先搜索（Breadth-First Search, BFS）
概念
广度优先搜索是一种搜索策略，它从起始节点开始，按照层次逐层向外扩展，直到找到目标或访问完所有节点。它优先关注的是路径的宽度。
核心特点
- 逐层探索：先访问当前层的所有节点，再访问下一层的节点。
- 使用队列结构：通过队列（FIFO）存储待访问的节点。
A/ \B C/ \
D E 还是以同样的图为例，从节点 A 出发，其访问顺序为： A → B → C → D → E，其搜索过程如下：
- 从
A出发，访问A。 - 访问
A的所有直接相邻节点：B和C。 - 访问
B的相邻节点：D和E。
实现
from collections import dequedef bfs(start):queue = deque([start]) # 初始化队列visited = set() # 用于存储已访问的节点while queue:node = queue.popleft() # 从队列头部取出一个节点if node not in visited:visited.add(node) # 标记为已访问print(node) # 访问当前节点queue.extend(graph[node]) # 将相邻节点加入队列
两者对比
| 属性 | 深度优先搜索 (DFS) | 广度优先搜索 (BFS) |
| 搜索策略 | 一条路径深入到底，无法继续时回溯。 | 按层次逐层搜索，每层节点按宽度扩展。 |
| 数据结构 | 栈（递归或显式栈）。 | 队列（FIFO）。 |
| 适用场景 | 适用于寻找深度路径，如迷宫寻路问题。 | 适用于寻找最短路径，如图的最短路径问题。 |
| 时间复杂度 | O(V+E)，其中 V 是顶点数，E 是边数。 | O(V+E)，与 DFS 相同。 |
| 空间复杂度 | 最坏情况下需要存储所有递归栈帧。 | 需要存储整个图的一层节点。 |
| 实现难度 | 易于实现，递归实现尤为简单。 | 需要显式维护队列，相对复杂一些。 |
感谢阅读，希望对你有所帮助~