leetcode-电话号码的字母组合
2024-10-21 13:12:39
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
已经是二刷这道题了,中间还有复习过这道题,今天回想起来,只记得在backTrace(int len)中要不断变化len的长度了。
我总结的回溯思想:回溯和递归很相似,都是属于探索,计算机的思维。一个简单的例子,走迷宫,回溯是沿着一条路一直走下去,一直到头 发现是死路,那么返回。
每走到一个分叉,都会分支成不同的路径继续探索下去。因此需要添加一个返回的边界条件 if() return; 同时判断不同的路径进行不同backTrace()
核心还是回溯中间的过程,
思路:这道题的回溯思想是,digits的每个位数代表了探索的步数。"23"中的2,可以分支成“a,b,c",然后沿着a,b,c三条路继续向后面添加字符串,ad,ae,af,bd,be,bf,cd.ce.cf。
class Solution { public List<String> letterCombinations(String digits) {
List<String> list=new ArrayList();
if(digits.length()==0)return list;
String s="";
backTrace(s,digits,0,list);
return list;
}
void backTrace(String s,String digits,int len,List<String> list){
String[] a={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
if(len==digits.length()){
list.add(s);
return;
}
String chars=a[digits.charAt(len)-'0'];
for(int i=0;i<chars.length();i++){
//如果这里写的是s=s+chars.charAt(i),而不是写在backTrace()中,会造成字符串增长,因为回溯的每一个结果都与其他结果无关
backTrace(s+chars.charAt(i),digits,len+1,list);
} }
}
知道总共有3*3种结果,我原本的思路是用两层for循环来输出,外层是digits.length(),内层是a[digits.charAt(len)-'0'].length(),
我忽略了回溯里面有自然向下探索的机制。
思考的难点:list.add()应该添加在哪个地方,这是原来思考的代码。我把backTrace的第三个参数复杂化了,直接从0开始非常简洁。
最新文章
- C#基础-out与ref字段
- Docker容器时间与宿主机时间不一致的问题
- 20160929001 Guid生成
- 浅谈 HTTPS 和 SSL/TLS 协议的背景与基础
- Linux系统下安装MongoDB 指南
- Gaussian分布下Hinge损失的期望
- Create Stacked Canvas to Scroll Horizontal Tabular Data Blocks In Oracle Forms
- WordPress WP-Realty插件‘listing_id’参数SQL注入漏洞
- localstorage || globalStorage || userData
- Tex介绍
- Java程序员们最常犯的10个错误(转)
- UNIX网络编程卷1 server编程范式0 迭代server
- Chapter 1 First Sight——10
- pureMVC简单示例及其原理讲解一(开篇)
- 怎样做才是最优雅方式切换 web 项目数据源 ?
- iOS开发添加pch文件
- Linux记录-GC值
- angular之指令
- hive笔记:复杂数据类型-map结构
- Java并发编程的艺术读后总结
热门文章
- java中prepareStatement与createStatement的区别
- python单元测试unittest框架
- Classless Interdomain Routing (CIDR)
- Entity Framework code first设置不在数据库中生成外键
- STM32F103 ucLinux开发之四(内核启动后的调试)
- 阿里云云服务器Windows Server 2012 R2无法安装IIS等组件的解决办法
- 更新UI放在主线程的原因
- es6新特性之 class 基本用法
- vuejs 预渲染插件 prerender-spa-plugin 生成多页面 -- SEO
- C++函数调用之——值传递、指针传递、引用传递