###### tags: `Leetcode`
# 0017. 电话号码的字母组合
Link: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
## 思路

## Keypoints
## Code in C++

## Code in Java

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

    private void dfsCombinations(List<String> res, HashMap<Character, String> map, String digits, int index, StringBuffer combination) {
        if (index == digits.length()){
            res.add(combination.toString());
        } else {
            String letters = map.get(digits.charAt(index));
            for (int i = 0; i < letters.length(); i++) {
                combination.append(letters.charAt(i));
                dfsCombinations(res, map, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

## 思路1
### 回溯

## 思路2
### 队列
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/hui-su-dui-lie-tu-jie-by-ml-zimingmeng/

这个思路很像层序遍历二叉树

class Solution {
        public List<String> letterCombinations(String digits) {
        int len = digits.length();
        if (len == 0) return new ArrayList<String>();
        HashMap<Character, String> numLetters = new HashMap<>();
        numLetters.put('2', "abc");
        numLetters.put('3', "def");
        numLetters.put('4', "ghi");
        numLetters.put('5', "jkl");
        numLetters.put('6', "mno");
        numLetters.put('7', "pqrs");
        numLetters.put('8', "tuv");
        numLetters.put('9', "wxyz");
        List<String> res = new LinkedList<>();
        Deque<String> queue = new ArrayDeque<>();
        queue.addLast("");
        for (int i = 0; i < digits.length(); i++) {
            char num = digits.charAt(i);
            String letters = numLetters.get(num);
            int lenQueue = queue.size();
            for (int j = 0; j < lenQueue; j++) {
                String tmp = queue.removeFirst();
                for (int k = 0; k < letters.length(); k++) {
                    queue.addLast(tmp + letters.substring(k, k + 1));
                }
            }
        }
        while (!queue.isEmpty()) {
            res.add(queue.removeFirst());
        }
        return res;
    }
}