题目描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例：
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明：
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
分析：
可以抽象成一个排列组合的问题，题目的意思就是说当输入"23"的时候实际上就是按了两次按键，分别是2和3，然后2对应的是abc，3对应的是def，所以我们只需递归遍历每一种结果即可解决问题。
代码如下：
class Solution { // 用map来映射数字和字母的对应关系 Map<String, 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"); } public List<String> letterCombinations(String digits) { // 用来存放所有结果的集合 List<String> list = new ArrayList<>(); int length = digits.length(); // 常规的先判断字符串长度，也是递归的结束条件 if (length == 0) { return list; } else if (length == 1) { list.addAll(Arrays.asList(map.get(digits).split(""))); return list; } else { // 截取字符串进行递归，就是每次都从下标1开始截取，那么最后就会先从digits的最后一位开始计算 List<String> list1 = letterCombinations(digits.substring(1)); // 然后取出数字，再从map中找到对应的字母 String s1 = map.get(digits.charAt(0)+""); // 双层for循环用来遍历所有结果，并添加到list中 // PS：这里也可以抽象出一个方法，然后用单层for再去递归 for (int i = 0; i < s1.length(); i++) { for (String s : list1) { list.add(s1.charAt(i) + s); } } return list; } } }
总结：
时间复杂度…反正很复杂就对了。这类排列组合问题一般都是用递归来解决，缺点就是时间复杂度过高。
