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）

        概念

        深度优先搜索是一种搜索策略，它会沿着一个路径不断深入到树或图的叶子节点，直到不能再继续深入为止，然后回溯到上一个分支点继续探索其他路径。它优先关注的是路径的深度。

        核心特点

1. 深入探索：优先沿着路径一直深入到底。
2. 回溯机制：在某路径不能继续深入时，回到上一个分支点继续探索。
3. 使用栈结构：可以用递归（隐式栈）或显式栈实现。

    A/ \B   C/ \
D   E# 其邻接表的结构如下：
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': [],'F': []
}

以图中的搜索为例，假设我们从节点 A 出发，目标是访问所有节点，则深度优先的访问顺序为：A → B → D → E → C，其搜索过程如下：

1. 从 A 出发，访问 B。
2. 从 B 深入到 D，访问 D。
3. 从 D 回溯到 B，然后访问 E。
4. 从 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）

        概念

        广度优先搜索是一种搜索策略，它从起始节点开始，按照层次逐层向外扩展，直到找到目标或访问完所有节点。它优先关注的是路径的宽度。

        核心特点

1. 逐层探索：先访问当前层的所有节点，再访问下一层的节点。
2. 使用队列结构：通过队列（FIFO）存储待访问的节点。

    A/ \B   C/ \
D   E

        还是以同样的图为例，从节点 A 出发，其访问顺序为： A → B → C → D → E，其搜索过程如下：

1. 从 A 出发，访问 A。
2. 访问 A 的所有直接相邻节点：B 和 C。
3. 访问 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 相同。
空间复杂度	最坏情况下需要存储所有递归栈帧。	需要存储整个图的一层节点。
实现难度	易于实现，递归实现尤为简单。	需要显式维护队列，相对复杂一些。

感谢阅读，希望对你有所帮助~