当前位置: 首页 > news >正文

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(3^n * 4^m)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 的所有直接相邻节点:BC
  3. 访问 B 的相邻节点:DE

        实现

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 相同。
空间复杂度最坏情况下需要存储所有递归栈帧。需要存储整个图的一层节点。
实现难度易于实现,递归实现尤为简单。需要显式维护队列,相对复杂一些。

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

相关文章:

LeetCode题解:17.电话号码的数字组合【Python题解超详细,回溯法、多叉树】,知识拓展:深度优先搜索与广度优先搜索

题目描述 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 示例 1&#xff1a; 输入&#xff1a;digits "23" 输出…...

《JVM第10课》内存溢出(OOM)排查过程

文章目录 常用命令1. jps2. jconsole3. jstat4. jmap 工具1.jvisualvm 排查OOM的方法其实很简单很简单。 如果能找到拋OOM的日志&#xff0c;可以在日志里看到是哪一行抛出的OOM异常。如果找不到日志&#xff0c;那么处理方式是导出Java进程的内存快照&#xff0c;然后用工具查…...

Thinkphp6视图介绍

一.MVC MVC 软件系统分为三个基本部分&#xff1a;模型&#xff08;Model&#xff09;、视图&#xff08;View&#xff09;和控制器&#xff08;Controller&#xff09; ThinkPHP6 是一个典型的 MVC 架构 控制器—控制器&#xff0c;用于将用户请求转发给相应的Model进行处理&a…...

躺平成长-人工智能进行编程-(12)

躺平成长&#xff1a; 让每一个人在科技&#xff08;开源的网络/智能科技对于生活琐事的处理&#xff09;的帮助下&#xff0c;实现养生反卷&#xff0c;躺平成长。 开源竞争&#xff1a; 当你无法彻底掌握技术的时候&#xff0c;你就开源这个技术&#xff0c;形成技术依赖&a…...

计算机网络中的域名系统(DNS)及其优化技术

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 计算机网络中的域名系统&#xff08;DNS&#xff09;及其优化技术 计算机网络中的域名系统&#xff08;DNS&#xff09;及其优化…...

Matplotlib库中show()函数的用法

在Matplotlib库中使用show()函数是用于显示绘制的图形的函数。它将图形显示在屏幕上或保存到文件中。show()函数通常在绘制完图形后调用。 Matplotlib是一个用于绘制2D图形的Python库&#xff0c;它提供了丰富的绘图工具和函数&#xff0c;可以用于创建各种类型的图表&#xf…...

C#中object和dynamic

在C#中&#xff0c;object和dynamic都是用于存储不同类型值的类型&#xff0c;但它们之间存在一些关键的区别&#xff1a; object object是C#中的基元类型之一&#xff0c;是所有其他类型的最终基类。当你将一个值赋给object类型的变量时&#xff0c;编译器会执行装箱操作&am…...

Spring Cloud Eureka 服务注册与发现

Spring Cloud Eureka 服务注册与发现 一、Eureka基础知识概述1.Eureka两个核心组件2.Eureka 服务注册与发现 二、Eureka单机搭建三、Eureka集群搭建四、心跳续约五、Eureka自我保护机制 一、Eureka基础知识概述 1.Eureka两个核心组件 Eureka Server &#xff1a;服务注册中心…...

【WPF】Prism学习(三)

Prism Commands 1.复合命令&#xff08;Composite Commanding&#xff09; 这段内容主要介绍了在应用程序中如何使用复合命令&#xff08;Composite Commands&#xff09;来实现多个视图模型&#xff08;ViewModels&#xff09;上的命令。以下是对这段内容的解释&#xff1a; …...

1+X应急响应(网络)系统加固:

系统加固&#xff1a; 数据库的重要性&#xff1a; 数据库面临的风险&#xff1a; 数据库加固&#xff1a; 业务系统加固&#xff1a; 安全设备加固&#xff1a; 网络设备加固&#xff1a;...

使用 Grafana api 查询 Datasource 数据

一、使用grafana 的api 接口 官方API 二、生成Api key 点击 Administration -》Users and accss -》Service accounts 进入页面 点击Add service account 创建 service account 点击Add service account token 点击 Generate token , 就可以生成 api key 了 三、进入grafana…...

【电子设计】按键LED控制与FreeRTOS

1. 安装Keilv5 打开野火资料,寻找软件包 解压后得到的信息 百度网盘 请输入提取码 提取码:gfpp 安装526或者533版本都可以 下载需要的 F1、F4、F7、H7 名字的 DFP pack 芯片包 安装完 keil 后直接双击安装 注册操作,解压注册文件夹后根据里面的图示步骤操作 打开说明 STM…...

JMeter中添加请求头

在JMeter中添加请求头的步骤如下&#xff1a; 1.打开HTTP信息头管理器 &#xff1a; 首先&#xff0c;你需要进入JMeter的HTTP请求组件。这可以通过在HTTP请求测试元素上右键点击&#xff0c;然后选择“添加 > 配置元件 > HTTP信息头管理器”来完成。 2.添加新的请求头…...

VMD + CEEMDAN 二次分解,CNN-LSTM预测模型

往期精彩内容&#xff1a; 时序预测&#xff1a;LSTM、ARIMA、Holt-Winters、SARIMA模型的分析与比较 全是干货 | 数据集、学习资料、建模资源分享&#xff01; EMD变体分解效果最好算法——CEEMDAN&#xff08;五&#xff09;-CSDN博客 拒绝信息泄露&#xff01;VMD滚动分…...

【Linux系统编程】第四十六弹---线程同步与生产消费模型深度解析

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】 目录 1、Linux线程同步 1.1、同步概念与竞态条件 1.2、条件变量 1.2.1、认识条件变量接口 1.2.2、举例子认识条件变量 1.2.3、…...

VoIP是什么?

IP 语音 (VoIP)&#xff08;Voice over Internet Protocol&#xff09; 是一种通过互联网拨打电话的方法。与旧的固定电话系统不同&#xff0c;互联网并非设计用于在连接的人之间实时传输音频信号。必须构建专门的技术和协议才能使之成为可能&#xff0c;这些技术和协议构成了 …...

MySQL 中的集群部署方案

文章目录 MySQL 中的集群部署方案MySQL ReplicationMySQL Group ReplicationInnoDB ClusterInnoDB ClusterSetInnoDB ReplicaSetMMMMHAGalera ClusterMySQL ClusterMySQL Fabric 总结参考 MySQL 中的集群部署方案 MySQL Replication MySQL Replication 是官方提供的主从同步方…...

《设计模式》创建型模式总结

目录 创建型模式概述 Factory Method: 唯一的类创建型模式 Abstract Factory Builder模式 Prototype模式 Singleton模式 最近在参与一个量化交易系统的项目&#xff0c;里面涉及到用java来重构部分vnpy的开源框架&#xff0c;因为是框架的搭建&#xff0c;所以会涉及到像…...

Conda安装与使用中的若干问题记录

Conda安装与使用中的若干问题记录 1.Anaconda 安装失败1.1.问题复述1.2.问题解决&#xff08;安装建议&#xff09; 2.虚拟环境pip install未安装至本虚拟环境2.1.问题复述2.2.问题解决 3.待补充 最近由于工作上的原因&#xff0c;要使用到Conda进行虚拟环境的管理&#xff0c;…...

人力资源招聘系统的革新之路:从传统到智能的转变

在全球化与数字化交织的今天&#xff0c;企业间的竞争日益激烈&#xff0c;而人才作为企业发展的核心驱动力&#xff0c;其重要性不言而喻。传统的人力资源招聘方式&#xff0c;如依赖纸质简历、人工筛选、面对面面试等&#xff0c;不仅效率低下&#xff0c;且难以精准匹配企业…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...