文章目录
- 题目
- 方法一:递归+回溯
题目
方法一:递归+回溯
参考讲解:还得用回溯算法!| LeetCode:17.电话号码的字母组合
首先可以画出树图:
- 先将数字对应的字符集合 加入到一个map集合
- 这里需要一个index来控制取数的范围,例如"2 3" 第一次index ==0 代表取 数字2 并且根据2可以从map中取出 2 对应的字符串
- 最终结果集在递归结束的时候收获,也就是要么 index 大于了数字字符串的长度 或者就是最后的要收获的子结果集长度等于数字字符串的长度
代码图示:
class Solution {// 递归+回溯List<String> res = new ArrayList<>();//结果集Map<Character,String> map = null;//全局mappublic List<String> 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 ;i<s.length() ; i++){str.append(s.charAt(i));//加入子结果集dfsback(digits,index+1,str); //index+1 让下一次递归 到下一个数字去取str.deleteCharAt(str.length() - 1);//回溯删掉字符串最后一个字符}}
}