网站服务器有哪些类型有哪些类型有哪些类型有哪些,google网页搜索,dede网站,seo零基础入门到精通200讲题目描述 给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。 示例 1#xff1a;
输入#xff1a;digits 23
输出…题目描述 给定一个仅包含数字 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(combinationletter,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,pathletter)# 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(VE)其中 V 是顶点数E 是边数。O(VE)与 DFS 相同。空间复杂度最坏情况下需要存储所有递归栈帧。需要存储整个图的一层节点。实现难度易于实现递归实现尤为简单。需要显式维护队列相对复杂一些。 感谢阅读希望对你有所帮助~
