leetcode hot100------17.电话号码的字母组合

回溯（backtrack）：
穷举多维度数据的方法，可以想作是多维度的exhaustive search详尽的搜索.

大意是：把多维度数据看作是一个多维向量（solution vector），然后运用递回依序递回穷举各个维度的值，制作出所有科恩个数据（solution space），并且在递回途中避免列举出不正确的数据。

 backtrack([v1,...,vn])  {  //[v1,...,vn]是多维度的向量
 //制作出了一组数据，并检验这组数据正不正确
 if([v1,...,vn] is well  - generated){
 	if([v1,...,vn] is a solution) process solution;
 	return;
 }
 //穷举这个维度的所有值，并递回到下一个维度
 for(x=possible values of vn + 1)
 	backtrack([v1,...,vn, x]);
 }
 call backtrack ([]); //从第一个维度开始逐步穷举

class Solution {
    public List<String> letterCombinations(String digits) {
        //创建一个List，用来放组合的字母
        List<String> combinations = new ArrayList<String>();
        //如果输入的digits是空的，那么直接返回空的combinations
        if(digits.length() == 0){
            return combinations;
        }
        //创建一个hashmap，将phone数字对应的字母放进去
        Map<Character, String> phoneMap = new HashMap<Character, String>(){{
            put('2',"abc");
            put('3',"def");
            put('4',"ghi");
            put('5',"jkl");
            put('6',"mno");
            put('7',"pqrs");
            put('8',"tuv");
            put('9',"wxyz");

        }};
        //新建一个backtrack回溯
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }
    public void backtrack (List<String> combinations, 
                           Map<Character, String> phoneMap,
                           String digits,
                           int index,
                           StringBuffer combination){
        //index？？？
        if(index == digits.length()){
            //用于返回一个表示指定char值的String对象，将combination的值转化成字符串string
            combinations.add(combination.toString());
        }
        else{
        //string.charAt()--> 用于返回制定索引处的字符
        //使用 charAt(int index)方法是一个能够用来检索特定索引下的字符的String实例的方法
        char digit = digits.charAt(index);
        //phoneMap.get(digit)-->phoneMap指定digit（key）对应的Value-->赋给letters
        String letters = phoneMap.get(digit);
        //letters的长度赋给lettersCount
        int lettersCount = letters.length();
        for (int i = 0; i < lettersCount; i++){
            //.append增加，往combination上增加letters对应key是i上的value
            combination.append(letters.charAt(i));
            //index + 1 ????
            backtrack(combinations, phoneMap, digits, index + 1, combination);
            combination.deleteCharAt(index);
        }
    }
   }
}

复杂度分析

时间复杂度：O(3^m
4^n)
，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，不同的字母组合一共有 3^m
4^n 种，需要遍历每一种字母组合。

空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。