LeetCode刷题系列 -- 17. 电话号码的字母组合

题目：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"

输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

思路： 本题适合用回溯法来解决，所谓回溯法，可以看成递归的一种高级使用，在递归调用前，让待构建的字符串从A状态达到一种新的状态B ，递归调用后，记住，要恢复原来的状态A 

具体思路

        回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。

       回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

public class Main{


  public List<String> letterCombinations(String digits) {
        Map<Character,List<Character>>  dict = new HashMap<>();
        dict.put('2',Arrays.asList('a','b','c'));
        dict.put('3',Arrays.asList('d','e','f'));
        dict.put('4',Arrays.asList('g','h','i'));
        dict.put('5',Arrays.asList('j','k','l'));
        dict.put('6',Arrays.asList('m','n','o'));
        dict.put('7',Arrays.asList('p','q','r','s'));
        dict.put('8',Arrays.asList('t','u','v'));
        dict.put('9',Arrays.asList('w','x','y','z'));

        List<String>  result = new ArrayList<>();
        StringBuilder  stringBuilder = new StringBuilder();
        if(digits.length()==0){
            return result;
        }
        backtrack(result,0,stringBuilder,digits,dict);
        return result;

    }

    public void backtrack(List<String> result,int index,StringBuilder combination,String  digits,Map<Character,List<Character>>  dict){

        if(index == digits.length()){
            result.add(combination.toString());
        }else {
            List<Character>  characters = dict.get(digits.charAt(index));

            for(char c:characters){
                //以下三行就是回溯法的精髓，切记切记
                combination.append(c);
                backtrack(result,index+1,combination,digits,dict);
                combination.deleteCharAt(index);
            }
        }

    }

}