LeetCode第17题电话号码的字母组合

简介: 该文章介绍了 LeetCode 第 17 题电话号码的字母组合的解法,通过分析得出可使用递归和回溯的思想解决,避免循环穷举的高循环次数,并给出了具体的编码实现,同时总结了该题较难理解,需要了解递归的本质,当嵌套循环层次多时可考虑递归。

继续打卡算法题,今天学习的是LeetCode的第17题电话号码的字母组合,这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些帮助。

image.png

分析一波题目

看了这题目,肯定可以想到的就是穷举的方法,如果我们使用循环的解法,循环次数就非常多了,这里我们可以借助递归和回溯的思想。

比如23

2-> abc

3-> def

循环穷举解法:

for(int i=0; i<'abc'.length(); i++) {
   
   

    for(int j=0; j<'def'.length(); j++ ){
   
   
        //组合字母
        //如果有3个数字 那么这里就3层循环了。
    }

}

递归解法(这里难理解):

//记录
StringBuilder temp = new StringBuilder();
//获取某一个串并遍历
for(int i=0; i<'abc'.length(); i++) {
   
   
    temp.append(str.charAt(i));
    //调用递归函数 不是直接写循环
    backfun()

}

编码解决

import java.util.*;

class Solution {
   
   
    ArrayList<String> list = new ArrayList<>();

    public ArrayList<String> letterCombinations(String digits) {
   
   
        //设置全局列表存储最后的结果
        if(digits== null || digits.length() == 0) {
   
   
            return list;
        }
        //初始对应所有的数字,为了直接对应2-9,新增了两个无效的字符串""
        String[] numString = {
   
   "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        //迭代处理
        backTracking(digits, numString, 0);
        return list;

    }

    //每次迭代获取一个字符串,所以会设计大量的字符串拼接,所以这里选择更为高效的 StringBuild
    StringBuilder temp = new StringBuilder();

    //比如digits如果为"23",num 为0,则str表示2对应的 abc
    public void backTracking(String digits, String[] numString, int num) {
   
   
        //遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
   
   
            list.add(temp.toString());
            return;
        }
        //str 表示当前num对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
   
   
            temp.append(str.charAt(i));
            //递归
            backTracking(digits, numString, num + 1);
            //剔除末尾的继续尝试 每一层都会删除 这就是回溯 第二层结束 ad ae af a 变成空串''
            temp.deleteCharAt(temp.length() - 1);
        }

    }
}

总结

这个题目比较难理解,需要了解递归的本质,如果嵌套循环的层次非常多的时候,可以想下是否可以通过递归解决。

相关文章
|
8天前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
2月前
|
存储 算法
LeetCode第49题字母异位词分组
LeetCode第49题"字母异位词分组"的解题方法,通过将每个字符串的字符排序后作为键存储在HashMap中,有效地将所有字母异位词分组。
LeetCode第49题字母异位词分组
|
4月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
4月前
|
存储 算法 安全
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
|
4月前
|
存储
力扣经典150题第四十二题:字母异位词分组
力扣经典150题第四十二题:字母异位词分组
25 0
|
4月前
|
存储
力扣经典150题第四十一题:有效的字母异位词
力扣经典150题第四十一题:有效的字母异位词
21 0
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
4月前
|
存储 算法 数据挖掘
leetcode第十七题:解密电话号码的字母组合与应用【python】
leetcode第十七题:解密电话号码的字母组合与应用【python】
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
45 6