电话号码的字母组合
程序员文章站
2022-06-05 13:38:47
...
今天的题目是电话号码的字母组合。
我们先来看下题目要求:
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
读完题,我们根据题意不难得出,题解是:求出所有输入的数字可能对应的字母组合,
如:① 2:‘'a",“b”,“c”
② 3:“d”,“e”,“f”
①和②组合搭配,可能返回的所有两位的字母。
如果还是没明白,还是来画出递归图读懂题意吧!
画着画着是不是就真的明白这个题大概啥意思啦!!好了,我们已经可以判定这个题可以使用深度优先搜索来做啦?
那么老规矩,先找出递归三要素。
一,函数设计
我们把可能出现的情况画出来,发现是个递归树,自然要传入一个数字 level表示需要遍历的层数,temp是为了存储临时变量,用StringBuilder而不用String是因为需要频繁修改,性能更高
/**
*
* @param level 当前树的层数
* @param temp 用来存储临时的值的容器,符合条件就放list中,不符合就回溯
*/
public void dfs(int level , StringBuilder temp) {
二,终止条件
输入几个数,level就是几,超出这个数就跳出循环
if (level >= input.length()) { // ②终止条件: 输入几个数字就是几层 超出就代表着已遍历完了
三,递归方向
输入的第 i 个数里头有几个元素 就有几个递归方向
需要注意的是回溯操作,回溯可以理解为将上一层树 (level)递归时产生的不符合条件的树杈干掉,换别的树杈
注:(因为符合条件就跳到终止条件了,那么最后一层不符合条件,但是也被存进ArrayList中了,不能让他把不符合的带走,所以需要回溯)
//递归方向:每一个输入的数字有几个元素就代表着几个方向
int num = (int) input.charAt(level) - '0';
for (int i = 0; i < chars[num].length; i++) {
dfs(level+1 , temp.append(chars[num][i]));
temp.deleteCharAt(temp.length() - 1);
}
函数体在这里,我们写这个函数来调递归函数。
在这里插入代码片
public List<String> letterCombinations(String digits){
input = digits;
if (!Objects.nonNull(digits))
if (Integer.parseInt(digits) >=2 && Integer.parseInt(digits) <=9)
return new ArrayList<>();
res = new ArrayList<>();
dfs(0,new StringBuilder());
return res;
}
String input;
ArrayList<String> res;
完整的代码在这里:
在这里插入代码片
char[][] chars = {{},{},{'a','b','c'},{'d','e','f'},
{'g','h','i'},{'j','k','l'},{'m','n','o'},
{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}
};
public List<String> letterCombinations(String digits){
input = digits;
if (!Objects.nonNull(digits))
if (Integer.parseInt(digits) >=2 && Integer.parseInt(digits) <=9)
return new ArrayList<>();
res = new ArrayList<>();
dfs(0,new StringBuilder());
return res;
}
String input;
ArrayList<String> res;
/**
*
* @param level 当前树的层数
* @param temp 用来存储临时的值的容器,符合条件就放list中,不符合就回溯
*/
public void dfs(int level , StringBuilder temp) {
if (level >= input.length()) { // ②终止条件: 输入几个数字就是几层 超出就代表着已遍历完了
res.add(temp.toString()); //将遍历完的数据添加到集合中
return;
}
//递归方向:每一个输入的数字有几个元素就代表着几个方向
int num = (int) input.charAt(level) - '0';
for (int i = 0; i < chars[num].length; i++) {
dfs(level+1 , temp.append(chars[num][i]));
temp.deleteCharAt(temp.length() - 1); //回溯操作,将上一层树递归时产生的不符合条件的树杈干掉,换别的树杈(因为符合条件就跳到终止条件了)
}
}
OK,程序写完啦,我们在main方法中测试下
搞定!
2020年11月25日21:18:01
下一篇: 算法复习 - AcWing位运算
推荐阅读
-
JavaEE基础day02 1.定义Java中的变量 四类八种 2.变量定义和使用的注意事项 3.数据类型的转换、强制数据类型转换4.算数运算符、比较运算符、逻辑运算符、赋值运算符、三元运算符
-
Java学习(五)——Java中的运算符
-
Shell中去除字符串里的空格或指定字符的方法
-
python try except 捕获所有异常的实例
-
Java入门五 常用的运算符
-
opencv提取旋转矩形区域的图像(将旋转矩形区域图像旋转成水平)
-
05. 数组的基本运算
-
webpack3、4的基本的使用方法
-
Qt4.7中 默认的构造函数
-
win10系统设备管理器没有端口怎么办 win10设备管理器没有端口的多种原因及解决方法