wordpress网站添加阅读全文,大连建网站,网站如何做诺顿认证,能看的网站给我一个呗文章目录 前言LeetCode、17. 电话号码的字母组合【中等#xff0c;dfs回溯】题目与类型思路递归回溯优化#xff1a;StringBuilder来回溯补充代码#xff1a;2024.1.31#xff08;简化#xff09; 资料获取 前言
博主介绍#xff1a;✌目前全网粉丝2W#xff0c;csdn博… 文章目录 前言LeetCode、17. 电话号码的字母组合【中等dfs回溯】题目与类型思路递归回溯优化StringBuilder来回溯补充代码2024.1.31简化 资料获取 前言
博主介绍✌目前全网粉丝2Wcsdn博客专家、Java领域优质创作者博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引博客目录索引(持续更新)
视频平台b站-Coder长路 LeetCode、17. 电话号码的字母组合【中等dfs回溯】
题目与类型 学习leetcode题解 题目链接17. 电话号码的字母组合
题目内容给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
题目类型搜索与图论/回溯、基础算法/枚举
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 思路
本题是要得到所有电话号码的字母组合这实际上就是全排列dfs其中就包含回溯的一个操作处理我们可以使用一个临时保留或者尝试使用回溯思路来实现。 递归回溯
思路由于循环的个数不确定则需要使用递归来进行求解。
代码时间复杂度O(3m×4n)、空间复杂度O(mn)
class Solution {/*** 根据指定字符生成字符串* param ch 数字字符* return*/public String generateNumtoString(char ch){String[] arr new String[] {abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};if (ch - 2 arr.length){return arr[ch - 2];}return null;}private ListString letters new ArrayList();/*** 全排列 abc、def、ghip* param arr 数组集合* param curIndex 当前要遍历的指定数组* param curArrIndex 当前排列的个数* param genStr 当前生成的字符串*/public void quanpailie(String[] arr, int curIndex, int curArrIndex, String genStr){//生成每组的排列个数if(curArrIndex arr.length){letters.add(genStr);return;}String curArr arr[curIndex];//取得当前要遍历的数组String temp genStr; //临时保存原先状态for (int i 0; i curArr.length(); i) { //枚举所有情况genStr curArr.charAt(i);quanpailie(arr,curIndex 1, curArrIndex 1, genStr);genStr temp; //回溯}}public ListString letterCombinations(String digits) {if (Objects.equals(,digits)){return new ArrayList();}String[] arrs new String[digits.length()];for (int i 0; i digits.length(); i) {arrs[i] generateNumtoString(digits.charAt(i));}//使用全排列进行求解quanpailie(arrs,0, 0, );return letters;}}小优化对于回溯操作的字符串替换使用StringBuilder时间、空间效率大幅度提升
public void quanpailie(String[] arr, int curIndex, int curArrIndex, StringBuilder str){...for (int i 0; i curArr.length(); i) { str.append(curArr.charAt(i));...str.deleteCharAt(curArrIndex);//回溯优化}
}优化StringBuilder来回溯
思路核心优化点就是在字符串回溯、拼接上
/*** 根据指定字符生成字符串* param ch 数字字符* return*/
public String generateNumToStr(char ch){String[] arr new String[] {abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};if (ch - 2 arr.length){return arr[ch - 2];}return null;
}private ListString letters new ArrayList();/*** 全排列 abc、def、ghip* param phones 电话数字映射的字符串数组* param index 当前排列的数字位置* param genStr 当前生成的字符串*/
public void quanpailie(String[] phones, int index, StringBuilder genStr){//生成每组的排列个数if(index phones.length){letters.add(genStr.toString());return;}String curArr phones[index];//取得当前要遍历的数组for (int i 0; i curArr.length(); i) { //枚举所有情况genStr.append(curArr.charAt(i));quanpailie(phones,index 1, genStr);genStr.deleteCharAt(index);}
}public ListString letterCombinations(String digits) {if (Objects.equals(,digits)){return new ArrayList();}String[] arrs new String[digits.length()];for (int i 0; i digits.length(); i) {arrs[i] generateNumToStr(digits.charAt(i));}//使用全排列进行求解quanpailie(arrs,0, new StringBuilder());return letters;
}补充代码2024.1.31简化
class Solution {ListString res new ArrayList();//23public ListString letterCombinations(String digits) {if (.equals(digits)) return res;//2-9String[] phones {abc,def,ghi,jkl, mno,pqrs,tuv,wxyz};ListString phoneList new ArrayList();for (int i 0; i digits.length(); i) {char ch digits.charAt(i);int num ch - 0;if (num 2) continue;phoneList.add(phones[num - 2]);}dfs (0, digits.length(), new StringBuilder(), phoneList);return res;}public void dfs (int curLevel, int allLevel, StringBuilder str, ListString phoneList) {//若是层数已经超越了原本的电话拨号数那么直接添加到集合中if (curLevel allLevel) {res.add(str.toString());return;}//当前层编号String phones phoneList.get(curLevel);for (int i 0; i phones.length(); i) {str.append(phones.charAt(i));dfs (curLevel 1, allLevel, str, phoneList);str.deleteCharAt(str.length() - 1);//回溯}}
}资料获取
大家点赞、收藏、关注、评论啦~
精彩专栏推荐订阅在下方专栏
长路-文章目录汇总算法、后端Java、前端、运维技术导航博主所有博客导航索引汇总开源项目Studio-Vue—校园工作室管理系统(含前后台SpringBootVue)博主个人独立项目包含详细部署上线视频已开源学习与生活-专栏可以了解博主的学习历程算法专栏算法收录
更多博客与资料可查看获取联系方式文末获取开发资源及更多资源博客获取 整理者长路 时间2024.1.31
