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.
We can draw out the solution space tree and then dfs traverse this tree.
For example, input is "23"
‘ ‘
/ | \
‘a‘ ‘b‘ ‘c‘
/ | \ / | \ / | \
‘d‘ ‘e‘ ‘f‘‘d‘ ‘e‘ ‘f‘ ‘d‘ ‘e‘ ‘f‘
Two java tricks:
Convert String to int: Integer.parseInt(string);
Convert char to int: Character.getNumericValue(element.charAt(2));
1 public class Solution { 2 public static final char[][] telephone = { 3 {‘a‘,‘b‘,‘c‘,‘ ‘}, 4 {‘d‘,‘e‘,‘f‘,‘ ‘}, 5 {‘g‘,‘h‘,‘i‘,‘ ‘}, 6 {‘j‘,‘k‘,‘l‘,‘ ‘}, 7 {‘m‘,‘n‘,‘o‘,‘ ‘}, 8 {‘p‘,‘q‘,‘r‘,‘s‘}, 9 {‘t‘,‘u‘,‘v‘,‘ ‘}, 10 {‘w‘,‘x‘,‘y‘,‘z‘} 11 }; 12 13 public List<String> letterCombinations(String digits) { 14 List<String> result = new ArrayList<String>(); 15 if (digits == null || digits.length() < 1) 16 return result; 17 dfs(digits, 0, new ArrayList<Character>(), result); 18 return result; 19 } 20 21 private void dfs(String digits, int start, List<Character> list, List<String> result) { 22 if (start < 0) 23 return; 24 if (start >= digits.length()) { 25 int size = list.size(); 26 StringBuilder sb = new StringBuilder(size); 27 for (char tmpChar : list) 28 sb.append(tmpChar); 29 result.add(sb.toString()); 30 return; 31 } 32 // Convert char to int 33 int index = Character.getNumericValue(digits.charAt(start)); 34 if (index < 2 || index > 9) 35 return; 36 char[] chars = telephone[index - 2]; 37 for (char tmpChar : chars) { 38 if (tmpChar != ‘ ‘) { 39 list.add(tmpChar); 40 dfs(digits, start + 1, list, result); 41 list.remove(list.size() - 1); 42 } 43 } 44 } 45 }
Letter Combinations of a Phone Number 解答
原文：http://www.cnblogs.com/ireneyanglan/p/4888458.html