欢迎来到Introzo百科
Introzo百科
当前位置：网站首页 > 技术 > 力扣17.电话号码字母组合

力扣17.电话号码字母组合

日期：2023-09-30 18:56

文章目录

  • 标题
  • 思考
  • 代码和注释
  • 总结

标题

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

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

来源：LeetCode
链接：https://www.introzo.com/problems/letter-combinations-of-a-phone-number
版权归Leetcode网络所有。商业转载请联系官方授权。非商业转载请注明出处。

思考

  • 1。使用递归回溯得到组合
  • 2。之前，我们在数组中完成了递归。对于这两个数组，本题我们不需要startIdx来控制递归位置
  • 3。定义递归参数时一定要特别注意
  • 4。这道题的树形结构你想清楚了吗【其实每个按钮都是由一层组成的】

代码和注释

/**
        使用回溯
        1.确定递归函数的参数
        2. 结束条件
        3. 每轮递归做了什么
     */
类 解决方案 {
    //临时路径字符串
    StringBuilder pathStr = new StringBuilder ();
    //存储结果集
    列表<字符串>资源=新  ArrayList<>( );


    
    公共 列表<字符串> 字母组合(字符串数字) {
        //极端判断
        if(数字 == null  ||位数.长度()==0){
            返回资源;
        }
        //定义一个数组，存放字母字符串[] numToVal = {"", "",“abc”，“def”，“ghi”,"jkl",  "mno", "pqrs",  “tuv”， “wxyz”};

        倒缝(位数, numToVal, 0);
        返回资源;
    }
    //num用于标记数字的下标位置（只能控制num元素）
    公共 void 倒缝（字符串）  数字, 字符串[]  numToVal, int num){  
        //终止条件（从标题可以看出，我们要把几个数组组合成多少个元素）
        //num控制for循环，即深度
        if(数字.长度() == num){
            //收集结果
            res.add(pathStr.toString());返回;
        }
        //每轮递归需要做什么
        //获取我们按下的每个数字（ascii计算）
        字符串 str = numToVal[数字.》 charAt(num)  - '0'];
        //str.length()控制每层的宽度
        对于(int i = 0; i<str.长度 (); i++){
            pathStr.append(str.charAt(i ));
            倒缝(位数, numToVal, num + 1);
            //原路返回
            pathStr.deleteCharAt( pathStr.长度()  - 1） ;

        }



    }
}

总结

  • 1。在做这道题的时候，我对回溯有了一些新的认识。
    • a：我们使用的for循环中的条件实际上是我们每一层树节点的宽度
    • b：我们递归的终止条件是深度[实际上相当于我们目标值的长度。所以当我们走到对应的深度，得到对应的深度值时，就不需要向下递归去获取新的值了。 】

相关文章

最近发表
猜你喜欢
晋ICP备2023019875号 | Introzo百科

关灯