力扣17-电话号码的数字组合

devtools/2024/11/13 16:25:40/

力扣17-电话号码的数字组合

    • 思路
    • 代码

题目链接

思路

在这里插入图片描述
原题:
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”

思路:
电话号码中的一个数字可以对应到多个字母,例如2对应a、b、c。要求23对应的字母组合,就是把2和3对应的字母进行组合。
在每次组合的过程中,一个数字只能取一个字母,不能连续两个字母来自同一个数字;
思考:
问题1:如何收集一个可能的组合?
问题2:在收集到一种组合后,如何继续收集第二种组合?
对于问题1:用暴力法可以解决,每层循环枚举一个数字对应的字母,但是电话号码串很长,循环嵌套深,代码不易好编写
可以采用递归的方式,每层进入递归函数,尝试一个数字对应的点好号码
进入函数,可以想向成进入一棵树的下一层,当递归的深度到达电话号码长度,即到达叶子节点,则返回。
问题3:在递归的每一层做什么?
递归纵向是进入树下一层,即电话号码中的一个数字,在同一层,应该去枚举这个数字对应的字母,这样就可以将当前层的字母,与上一层的字母进行结合,形成答案的一部分,,
问题4:递归什么时候结束?
到达电话号码的长度时,应该往树的上一层返回。

这里的往下递,和往上归,即回溯法,往下遍历是搜索,往上是回溯;回退到上一层,当前数字对应的字母就丢弃了,
比如 2,3; 3是第二层,遍历得到的字母组合是ab, 已经达到电话号码长度,往上一层回溯时b应该就被丢弃。

因此,本题使用回溯法,纵向遍历电话号码中的每个数字,横向遍历每个数字对应的字母,达到电话号码长度时收集一种组合,并往上一层回溯。

代码

java">class Solution {private List<String> ans;private String[][] dic = {{"2","abc"},{"3","def"},{"4","ghi"},{"5","jkl"},{"6","mno"},{"7","pqrs"},{"8","tuv"},{"9","wxyz"}};public List<String> letterCombinations(String digits) {ans = new ArrayList<>();if (digits.length()==0) {return ans;}Map<String,String> m = new HashMap<>();for (int i=0, n=dic.length; i<n; i++) {m.put(dic[i][0]+"", dic[i][1]+"");}String path = "";dfs(digits, m, 0, path);return ans;}public void dfs(String digits, Map<String, String> mp, int i, String path) {int n = digits.length();if (i>=n) {ans.add(new String(path));return;}String t = mp.get(digits.charAt(i)+"");for (int j=0, m=t.length(); j<m; j++) {dfs(digits, mp, i+1, path+t.charAt(j));}}
}

http://www.ppmy.cn/devtools/133034.html

相关文章

小型的网站服务器该如何选择配置?

对于选择小型网站服务器的配置主要根据企业网站的发展规模&#xff0c;以及网站业务的发展需求&#xff0c;下面就让我们来具体了解一下小型的网站服务器该怎样选择吧&#xff01; 首先企业需要按照每个月的网站访问量和数据的传输量&#xff0c;选择适合自己的网络带宽与流量限…

**AI的三大支柱:神经网络、大数据与GPU计算的崛起之路**

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

如何用python求导数

打开python运行环境。 导入微分的模块包&#xff1a;from sympy import *。 定义符号变量&#xff1a;x symbols(x) 定义一个函数&#xff1a;f x**9 diff diff(f,x)求导 最后输入diff&#xff0c;即可显示其变量值了。

Java接收xml格式参数转为json

1、定义实体类 import javax.xml.bind.annotation.XmlElement; import javax.xml.bind.annotation.XmlRootElement;XmlRootElement(name "User") Setter ToString public class User {private String name;XmlElement(name "username")public String ge…

【网络安全 | 甲方安全建设】分布式系统、Redis分布式锁及Redisson看门狗机制

未经许可,不得转载。 文章目录 分布式系统分布式系统的核心特性分布式系统的典型架构分布式锁概念Redis 分布式锁原理互斥性锁释放锁的唯一性具体实现Redisson分布式锁分布式系统 分布式系统是一种由多台计算机(节点)组成的系统,这些节点通过网络相互连接并协同工作,共同…

基于python的天气数据采集与可视化分析,对20个城市的天气适宜出行度分析

摘要 本项目旨在基于Python对20个城市的天气数据进行采集与可视化分析&#xff0c;以评估天气的适宜出行度。该分析通过四个主要指标进行量化&#xff0c;这些指标分别是天气状况良好率、空气质量优良率、气温适宜率和安全天气率。通过这些指标&#xff0c;我们能够有效地判断…

【Linux】Ansible集中化运维工具(详解)安装、常用模块、playbook脚本

文章目录 一、Ansible安装及远程控制1、关闭防火墙和SELinux2、安装ansible3、配置SSH无密码登录1、在管理机上生成一对密钥2、将公钥下发到远程主机3、保管密钥 4、主机目录 二、常用模块1、setup模块2、copy模块3、file模块4、shell模块5、script模块6、ping模块7、group模块…

多模态PaliGemma——Google推出的基于SigLIP和Gemma的视觉语言模型(含SigLIP详解)

前言 本文怎么来的呢&#xff1f;其实很简单&#xff0c;源于上一篇文章《π0——用于通用机器人控制的流匹配VLA模型&#xff1a;一套框架控制7种机械臂(改造了PaliGemma和ACT的3B模型)》中的π0用到了PaliGemma 故本文便来解读下这个PaliGemma 第一部分 PaliGemma 1.1 Pal…