国外网站推广软件,应届生在淮北招的网站建设类型岗位,长春网站建设方案外包,高端的网站设计公司文章目录 题目方法一#xff1a;递归回溯 题目 方法一#xff1a;递归回溯
参考讲解#xff1a;还得用回溯算法#xff01;| LeetCode#xff1a;17.电话号码的字母组合 首先可以画出树图#xff1a;
先将数字对应的字符集合 加入到一个map集合 这里需要一个index来控… 文章目录 题目方法一递归回溯 题目 方法一递归回溯
参考讲解还得用回溯算法| LeetCode17.电话号码的字母组合 首先可以画出树图
先将数字对应的字符集合 加入到一个map集合 这里需要一个index来控制取数的范围例如2 3 第一次index 0 代表取 数字2 并且根据2可以从map中取出 2 对应的字符串最终结果集在递归结束的时候收获也就是要么 index 大于了数字字符串的长度 或者就是最后的要收获的子结果集长度等于数字字符串的长度 代码图示
class Solution {// 递归回溯ListString res new ArrayList();//结果集MapCharacter,String map null;//全局mappublic ListString letterCombinations(String digits) {if(digits.length() 0) return res;map new HashMap(){{//映射关系put(2, abc);put(3, def);put(4, ghi);put(5, jkl);put(6, mno);put(7, pqrs);put(8, tuv);put(9, wxyz);}};StringBuffer str new StringBuffer();//子结果集int index 0 ; //用于控制取到哪个数字了 初始默认取0第一个位置 2 dfsback(digits,index,str);return res;}public void dfsback(String digits,int index,StringBuffer str){// if(str.length() digits.length()){//递归结束 收获结果 这两个递归终止条件都是可以的if(index digits.length()){//递归结束 收获结果res.add(str.toString());return;}String s map.get(digits.charAt(index)); //取出index位置的数字 并且根据数字获取到对应的字符串for(int i 0 ;is.length() ; i){str.append(s.charAt(i));//加入子结果集dfsback(digits,index1,str); //index1 让下一次递归 到下一个数字去取str.deleteCharAt(str.length() - 1);//回溯删掉字符串最后一个字符}}
}
