• LeetCode-电话号码的字母组合(回溯)


    每日一题

    今天刷到的是一道利用回溯来解决的题,不过稍微有点复杂,并且我也有一段时间没有做回溯了,所有在解题时也是思考了一段时间。

    题目要求

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

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

    示例 1:

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

    示例 2:

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

    示例 3:

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

    题目解析

    本题中稍微复杂一点的地方在于每个数字对应着几个字符,在组合时要把每个数字对应的字符都尝试组合一次。整体的思路就是经典的回溯算法,通过递归调用方法,将每个字符组合进去后进去递归,递归结束后再移除出来,并且以后在此位置上不会再次将其组合。

    因此我通过一个map来储存数字对应的字符,在代码中通过map来获取到数字对应的字符。

    利用StringBuilder类型的特性来组合字符串和移除字符串中的字符。并且设置一个索引index来记录当前在组合第几个数。

    完整的方法思路为,如果当前已经组合的字符串长度等于dights的长度,则证明已经全部组合完成,将当前的字符串添加进结果中后直接返回。如果还未组合完成则通过index索引获取到当前的数字,再通过map找到对应的所有字符,通过遍历字符串,将字符串中的每一个字符组合进StringBuilder类型表示的当前字符串中,进行递归调用,递归结束后,将该字符移除,进入下一次循环。

    代码实现

    1. class Solution {
    2. public final List res = new ArrayList<>();
    3. public List letterCombinations(String digits) {
    4. if(digits.length()==0){
    5. return res;
    6. }
    7. Map map = new HashMap<>();
    8. map.put('2',"abc");
    9. map.put('3',"def");
    10. map.put('4',"ghi");
    11. map.put('5',"jkl");
    12. map.put('6',"mno");
    13. map.put('7',"pqrs");
    14. map.put('8',"tuv");
    15. map.put('9',"wxyz");
    16. find(map,digits,0,new StringBuilder());
    17. return res;
    18. }
    19. public void find(Map map,String digits,int index,StringBuilder s){
    20. if(s.length()==digits.length()){
    21. res.add(s.toString());
    22. return;
    23. }
    24. String cur = map.get(digits.charAt(index));
    25. for(int i =0;i
    26. char c = cur.charAt(i);
    27. s.append(c);
    28. find(map,digits,index+1,s);
    29. s.deleteCharAt(index);
    30. }
    31. }
    32. }

  • 相关阅读:
    【Vue2深度学习】虚拟DOM篇-Patch主流程
    螺杆支撑座应用领域合集
    LTE小区搜索过程及SCH/BCH设计
    计算机科学的奇趣探索
    数据结构之Map&Set
    C/C++多进程高并发框架分享【内附可执行源码注释完整】
    09-锚点&精灵图
    Python List 中的append 和 extend 的区别
    IDEA集成Git
    【仿真动画】ABB IRB 8700 机器人搬运(ruckig在线轨迹生成)动画欣赏
  • 原文地址:https://blog.csdn.net/m0_62902381/article/details/138047611