【算法Hot100系列】电话号码的字母组合

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。

• 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老
• 导航
  • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
  • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
  • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
  • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
  • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ?? 欢迎订阅本专栏 ??

一.题目描述

1.题目信息

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

2.题目地址

题目地址

3.测试示例

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

4.提示信息

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

二.题解

1.回溯算法

private static HashMap<Character, String> map = new HashMap<>();

static {
    map.put('2', "abc");
    map.put('3', "def");
    map.put('4', "ghi");
    map.put('5', "jkl");
    map.put('6', "mno");
    map.put('7', "pqrs");
    map.put('8', "tuv");
    map.put('9', "wxyz");
}

private List<String> res = new ArrayList<>();
private StringBuilder stringBuilder = new StringBuilder();

public List<String> letterCombinations(String digits) {
    if (digits.length() == 0) {
        return res;
    }
    //排列组合
    dfs(digits, 0);
    return res;
}

private void dfs(String digits, int index) {
    //遍历完了所以得数字
    if (index == digits.length()) {
        res.add(stringBuilder.toString());
        return;
    }
    //获取当前的数字-字符串
    String letters = map.get(digits.charAt(index));
    for (int i = 0; i < letters.length(); i++) {
        //逐个添加到结果集中
        stringBuilder.append(letters.charAt(i));
        //递归处理下一个字符
        dfs(digits, index + 1);
        //剪枝处理
        stringBuilder.deleteCharAt(index);
    }
}

2.解题思路

1. 将数字和字符串用 map 进行对应
2. 遍历每一个数字
3. 在遍历当前数字对应的字符串时,递归处理字符串的所有字符
4. 剪枝上一个数字

3.注意事项

• 数字和字符的对应关系
• 画一个排列组合树结构
• 回溯就是递归
• 剪枝的优化处理

三.自我分析

1.解题思路

if 有思路
    开写
else
    去看相关标签，确定具体解题方法
    if 有思路
        开写
    else
        看提示信息
        if 有思路
            开写
        else
            看答案

2.思考链路

• 没有思路
• 多做,多思考
• 形成自己的肌肉记忆
• 多多调试
• 多总结
• 多回头看看以前的题目,温故而知新

觉得有用的话点个赞 👍🏻 呗。
??????本人水平有限，如有纰漏，欢迎各位大佬评论批评指正！😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话，也请给个点赞、收藏下吧，非常感谢!👍 👍 👍

🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧！🌙🌙🌙