17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]

解法一：回溯法

遍历所有可能的结果，返回成功的结果

List res = new ArrayList<>();
    HashMap hash = new HashMap<>();

    public List letterCombinations(String digits) {
        if (digits.length() == 0)
            return new ArrayList<>();
        createHash();
        letter(digits, 0, new StringBuilder());
        return res;

    }

    void letter(String digits, int level, StringBuilder tempres) {

        if (level == digits.length()) {
            res.add(tempres.toString());
            return;
        }
        String str = hash.get(digits.charAt(level));
        for (int i = 0; i < str.length(); i++) {
            tempres.append(str.charAt(i));
            letter(digits, level + 1, tempres);
            tempres.deleteCharAt(tempres.length() - 1);
        }
    }

    void createHash() {
        hash.put('2', "abc");
        hash.put('3', "def");
        hash.put('4', "ghi");
        hash.put('5', "jkl");
        hash.put('6', "mno");
        hash.put('7', "pqrs");
        hash.put('8', "tuv");
        hash.put('9', "wxyz");
    }

时间复杂度：O(3m×4n)

空间复杂度：O(m+n)

解法二：队列

 HashMap hash = new HashMap<>();

    public List letterCombinations(String digits) {
        if(digits.length()==0)
        return new ArrayList<>();
        createHash();
        Deque queue = new LinkedList<>();
        queue.add("");
        for (int i = 0; i < digits.length(); i++) {
            int size = queue.size();

            for (int j = 0; j < size; j++) {
                String nowdigit = hash.get(digits.charAt(i));
                String curqueue = queue.poll();
                for (int k = 0; k < nowdigit.length(); k++)
                    queue.add(curqueue + nowdigit.charAt(k));
            }

        }
        List res = new ArrayList<>();
        int len = queue.size();
        for (int i = 0; i < len; i++)
            res.add(queue.poll());
        return res;

    }

    void createHash() {
        hash.put('2', "abc");
        hash.put('3', "def");
        hash.put('4', "ghi");
        hash.put('5', "jkl");
        hash.put('6', "mno");
        hash.put('7', "pqrs");
        hash.put('8', "tuv");
        hash.put('9', "wxyz");
    }

总结：心里要有层次遍历的树的结构