思路1：实质上就是一颗树，注意回溯条件

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        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(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()) {
            combinations.add(combination.toString());
        } else {
        	// 取出第index个数字
            char digit = digits.charAt(index);
            // 第index个数字对应的字母
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
            	// 合并字符
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                // 回溯，将字母删除  比如ad，删除d之后再拼接成ae，如果不删除会拼接成ade
                combination.deleteCharAt(index);
            }
        }
    }
}

思路2：队列，举个例子，输入23，2 对应的字母为abc，3 对应的字母为 def， 取出 a 和 def 组合后，再取出 b 跟def组合…

class Solution {
	//这里也可以用map，用数组可以更节省点内存
    String[] letter_map = {" ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.length() == 0)   return ans;
        //先往队列中加入一个空字符
        ans.add("");
        for (int i = 0; i < digits.length(); i++) {
        	// 第i个数字对应的字母
            String letters = letter_map[digits.charAt(i) - '0'];
            // 加入一个空字符后，ans.size() == 1
            int size = ans.size();
            //计算出队列长度后，将队列中的每个元素挨个拿出来(第一个元素为空)
            for (int j = 0; j < size; j++) {
                String s = ans.remove(0);
                for (int k = 0; k < letters.length(); k++) {
                	//然后跟"abc"这样的字符串拼接，并再次放到队列中 此时队列中就是abc
                    ans.add(s+letters.charAt(k));
                }
            }
        }
        return ans;
    }
}