原题： Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string “23” Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”,”cd”, “ce”, “cf”].
分析：求出由字母组合而成的集合，这些字母由给出的数字串中的单个数字来表示（如上图的电话按键）
思路是深度优先搜索，先取出一个数字，在深度遍历其余数字表示的字母，组成最后的字符串
public class Solution { public static List<String> letterCombinations(String digits) { List<String> result = new ArrayList<String>(); if(digits==null || digits.length()==0) return result; Map<String,String[]> map = new HashMap<String,String[]>(); map.put("2", new String[]{"a","b","c"}); map.put("3", new String[]{"d","e","f"}); map.put("4", new String[]{"g","h","i"}); map.put("5", new String[]{"j","k","l"}); map.put("6", new String[]{"m","n","o"}); map.put("7", new String[]{"p","q","r","s"}); map.put("8", new String[]{"t","u","v"}); map.put("9", new String[]{"w","x","y","z"}); dfs(digits,0,"",map,result);//深度优先搜索 return result; } private static void dfs(String digits, int dx, String path, Map<String, String[]> map, List<String> result) { if(digits.length()==path.length()){//遍历到最后，将遍历的路径也就是得到的字母组合加入集合 result.add(path); return ; } for (int i = dx; i < digits.length(); i++) { for (String s : map.get(digits.substring(i,i+1))) { dfs(digits,i+1,path+s,map,result); } } } }