LeetCode刷题笔记- 17. 电话号码的字母组合

题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

题解：
该题其实是一个二叉树的遍历问题：
我们采用递归的方法，深度优先遍历即可，代码如下：

class Solution {
//这里采用了一种特殊方式初始化HashMap，第一层括弧实际是定义了一个匿名内部类 (Anonymous Inner Class)，
//第二层括弧实际上是一个实例初始化块 (instance initializer block)，这个块在内部匿名类构造时被执行。
//这个块之所以被叫做“实例初始化块”是因为它们被定义在了一个类的实例范围内。
    Map<String,String> num_word=new HashMap<String,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");
        }
    };
    List<String> result=new ArrayList<>();
    public void DFS_Find(String now_letter,String remain_number){//now-letter是当前已经处理好数字对应的字母，remain_number是还未处理的数字串
        if(remain_number.length()==0) result.add(now_letter);//递归出口
        else{
            String number=remain_number.substring(0,1);//截取还未处理数字串的第一个数字作为接下来要处理的数字
            String letters=num_word.get(number);//将该数字可能对应的字母从HashMap中找出来
            for(int i=0;i<letters.length();i++){//将可能对应的字母一一截取出来，组合到now_letter后面作为新的now_letter，递归调用DFS_Find函数
                String letter_temp=letters.substring(i,i+1);
                DFS_Find(now_letter+letter_temp,remain_number.substring(1));
            }
        }
        
    }
    public List<String> letterCombinations(String digits) {
        //如果给出的数字串长度不为零则启动深度优先遍历
        if(digits.length()!=0) DFS_Find("",digits);
        return result;
    }
}

官方题解传送门