【算法攻坚】回溯电话号码

简介: 【算法攻坚】回溯电话号码

今日题目


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


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


image.png


示例 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'] 的一个数字。


思路


从示例上来说,输入"23",最直接的想法就是两层for循环遍历了,正好把组合的情况都输出了。


如果输入"234"呢,那么就三层for循环,如果"2345"呢,就四层for循环.......

所以这种暴力破解办法的算法复杂度是至少是O(3^len(digist)),所以要想别的方案

仔细观察题目,要完成这道题需要解决如下三个问题:


  • 数字和字母如何映射


  • 两个字母就两个for循环,三个字符我就三个for循环,以此类推,然后发现代码根本写不出来


  • 输入1 * #按键等等异常情况


对于这三个问题,相应的处理方式:


  • 只要是映射关系直接考虑map,这道题key是数字且连续的,所以同时可以用数组索引当做key


  • 这种情况可以利用回溯思想解决,回溯思想其实还是需要利用递归方程才能实现,把满足条件的场景存起来,然后回退,直到遍历完所有场景


  • 把主要的异常场景都要考虑到,不然算法题还是很难AC,可能需要多次调试


从上面分析可以看出最难点就是在回溯思想的实现:


  • 确定回溯函数参数


  • 确定终止条件


  • 确定单层遍历逻辑


解决方式:


  • 用StringBuilder存储一次遍历的结果


  • 什么时候算是一遍呢?其实是长度为输入数字的个数


  • 单层循环逻辑即为,单个数字对应的字符循环


对应实现


public class Solution {
    // 数字到号码的映射
    private final String[] map = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    // 路径
    private final StringBuilder path = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits == null || "".equals(digits)) {
            return Collections.emptyList();
        }
        List<String> result = new ArrayList<>();
        backtrack(result, digits, 0);
        return result;
    }
    // 回溯函数
    private void backtrack(List<String> result, String digits, int index) {
        if (path.length() == digits.length()) {
            result.add(path.toString());
            return;
        }
        String val = map[digits.charAt(index) - '2'];
        for (char c : val.toCharArray()) {
            path.append(c);
            backtrack(result, digits, index + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }


执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:37.2 MB, 在所有 Java 提交中击败了37.71%的用户


小结


回溯算法还是还好用的,除了占用内存比较大外,可能还有更好的解题方式,以后再分享吧,我们下道题见


今天多学一点。明天就少说一句求人的话


目录
相关文章
|
22天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
22天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
22天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
22天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
22天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
22天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
22天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
22天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
22天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
25天前
|
算法
”回溯算法“框架及练习题
”回溯算法“框架及练习题
34 0
下一篇
无影云桌面