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"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
题目含义：给定一个数字字符串（数字为0-9），请按手机的9宫格输入法得到所有可能的字母组合（上面举了个列子）。
1 public List<String> letterCombinations(String digits) { 2 if (digits.isEmpty()) return new ArrayList<>(); 3 LinkedList<String> ans = new LinkedList<String>(); 4 String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 5 ans.add(""); 6 for (int i = 0; i < digits.length(); i++) { 7 // int x = Character.getNumericValue(digits.charAt(i)); //效率不如下面的高 8 int x = digits.charAt(i) - ‘0‘; 9 int size = ans.size(); 10 // BFS理论，把上一层的string拿出来，加入新的字母后重新加入 11 for(int j=0;j<size;j++) 12 { 13 String t = ans.remove(); 14 for (char s : mapping[x].toCharArray()) 15 ans.add(t + s); 16 } 17 } 18 return ans; 19 }
17. Letter Combinations of a Phone Number
原文：http://www.cnblogs.com/wzj4858/p/7682659.html