回溯算法 17. 电话号码的字母组合
2023-02-26 09:46:34 时间
回溯算法 17. 电话号码的字母组合
回溯算法用于寻找所有的可行解,如果发现一个解不可行,则会舍弃不可行的解。
在这道题中,由于每个数字对应的每个字母都可能进入字母组合,因此不存在不可行的解,直接穷举所有的解即可。
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1
不对应任何字母。
示例 1:
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = ""
输出:[]
示例 3:
输入:digits = "2"
输出:["a","b","c"]
提示:
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
代码
public static List<String> letterCombinations(String digits) {
if ("".equals(digits)) {
return new ArrayList<>(0);
}
List<String> rsList = new ArrayList<>((int) Math.pow(3, digits.length()));
Map<Character, List<Character>> map = Map.of(
'2', List.of('a', 'b', 'c'), '3', List.of('d', 'e', 'f'),
'4', List.of('g', 'h', 'i'), '5', List.of('j', 'k', 'l'),
'6', List.of('m', 'n', 'o'), '7', List.of('p', 'q', 'r', 's'),
'8', List.of('t', 'u', 'v'), '9', List.of('w', 'x', 'y', 'z')
);
// 例:digits = "2"
generateString(digits, 0, rsList, map, new StringBuilder());
return rsList;
}
private static void generateString(String str, int p, List<String> list, Map<Character, List<Character>> map, StringBuilder sb) {
if (p == str.length()) {
list.add(sb.toString());
return;
}
// 'a', 'b', 'c'
for (Character ch : map.get(str.charAt(p))) {
// 1. a
// 2. b
// 3. c
sb.append(ch);
// 递归进入 p == 1 str.len == 1
// toString加入集合后返回
generateString(str, p + 1, list, map, sb);
// 1. 删除a
// 2. 删除b
// 3. 删除c
sb.deleteCharAt(p);
}
}
相关文章
- 一个新视角:前端框架们都卷错方向了?
- 编码中的Adapter,不仅是一种设计模式,更是一种架构理念与解决方案
- 入职字节跳动那一天,我哭了(蘑菇街被裁,奋战7个月拿下offer)
- 绝杀processOn,这款UML画图神器,阿里字节都用疯了,你还不知道?
- 关于状态机的技术选型,最后一个真心好!
- 聊聊 Java 19 新功能,你学会了吗?
- 深入浅出日志体系(logback最佳实践)
- github上fork2.4k,star8.7k的这款状态机,原来长这样!
- DiskSight for Mac(磁盘重复文件清理工具) v3.0激活版
- “喜提”一个P2级故障—CMSGC太频繁,你知道这是什么鬼?
- ACMMM 2022 | 首个针对跨语言跨模态检索的噪声鲁棒研究工作
- 即插即用!Batch Transformer
- 关于软件定时器的一些讨论
- Go 学习:那些不一样的知识点(上)
- 深入理解 ForkJoinPool:入门、使用、原理
- ACM MM 2022 Oral | PRVR: 新的文本到视频跨模态检索子任务
- 彻底了解线程池的原理—40行从零开始自己写线程池
- 「多语言图像描述」最强评估基准XM3600来了!涵盖36种语言
- 小扎亲自演示首个「闽南语」翻译系统!主攻3000种无文字的语言
- 曝苹果Mac Pro明春面世:彻底告别英特尔CPU,性能暴涨300%