17. 电话号码的字母组合

image.png

其实就是一个回溯问题
先将所有的字母利用hashmap存起来，然后找到index对应的那部分字母集合，然后遍历字母的集合，再去递归：back(digits,sb.append(s.charAt(i)),index+1);
同时递归必须要剪枝，所以将得到的字符串的最后一个字符删除

class Solution {
    Map<Character,String> map=new HashMap<Character,String>();
    List<String> res=new ArrayList<String>();
    public List<String> letterCombinations(String digits) {
        
        if(digits.length()==0) return new ArrayList<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        StringBuilder sb=new StringBuilder();
        back(digits,sb,0);
        return res;
    }
    public void back(String digits,StringBuilder sb,int index){
        if(sb.length()==digits.length()){
            res.add(sb.toString());
            return;
        }
        String s=map.get(digits.charAt(index));
        for(int i=0;i<s.length();i++){
            back(digits,sb.append(s.charAt(i)),index+1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}