leetcode–demo17电话号码的自由组合

这一题与46条全排列差不多，两个题一比较你就会发现这些题都是有套路的，都是dfs+回溯，知道题目考的什么算法那么处理起来就简单了。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res=new ArrayList<>();
        int n=digits.length();
        if (n==0){
            return res;
        }
        Map<Character,String> map=new HashMap<>();
        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");
        dfs(res,digits,map,0,new StringBuffer());
        return res;
    }

    private void dfs(List<String> res, String digits, Map<Character, String> map, int depth, StringBuffer stringBuffer) {
        if (depth==digits.length()){
            res.add(stringBuffer.toString());
            return;
        }
        String temp = map.get(digits.charAt(depth));
        for (int i=0;i<temp.length();i++){
            stringBuffer.append(temp.charAt(i));
            dfs(res,digits,map,depth+1,stringBuffer);
            //回溯
            stringBuffer.deleteCharAt(stringBuffer.length()-1);
        }
    }
}