本文共 4368 字，大约阅读时间需要 14 分钟。
问题：
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.Example: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.
官方难度：
Medium
翻译：
给定一个数字组成的字符串，返回所有可能的字母集合。数字和字母的映射关系就像电话上显示的一样。
例子：
输入字符串："23"
输出集合：["ad","ae","af","bd","be","bf","cd","ce","cf"]
集合内的元素顺序没有规定。
方法一：
方法一的解题代码：
1 public static ListletterCombinations(String digits) { 2 if (digits == null) { 3 throw new IllegalArgumentException("Input error"); 4 } 5 String copyDigits = digits; 6 while (copyDigits.length() > 0) { 7 int i = copyDigits.charAt(0) - '0'; 8 if (i < 2 || i > 9) { 9 throw new IllegalArgumentException("Input error");10 }11 copyDigits = copyDigits.substring(1);12 }13 // 只接受2-9的数值字符串14 List source = new LinkedList<>();15 if (digits.equals("")) {16 return source;17 }18 // 初始size需要等于1，不然之后不能循环19 source.add("");20 return format(source, digits);21 }22 23 // 递归方法24 private static List format(List source, String targetDigit) {25 if (targetDigit.length() == 0) {26 return source;27 }28 List result = new LinkedList<>();29 // 第一个数30 int first = targetDigit.charAt(0) - '0';31 char[] cArray = dict(first);32 // source集合和targetDigit第一个数字对应字典的全排列33 for (String str : source) {34 for (char c : cArray) {35 result.add(str + c);36 }37 }38 // 将target转成source，继续递归39 return format(result, targetDigit.substring(1));40 }41 42 private static char[] dict(int num) {43 String[] mappping = new String[] { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };44 return mappping[num - 2].toCharArray();45 }
方法二：
1. 转译字典还能使用其他方法实现，不使用字符串数组，获得返回的char型数组的第一个值，然后依次添加。
2. 有一个隐藏的性质，得到的每一个字母字符串长度，与最初的数字字符串长度是一样的。然后指定声明集合为LinkedList，利用LinkedList.remove()方法删除并返回第一个元素，以及LinkedList.peek()方法得到集合的第一个元素。
3. 利用三次循环，外循环获取对应数字，除了方法一中的办法，还可以使用Character包装类自带的方法：Character.getNumbericValue()。
4. 中循环，使用while()循环判断集合的第一个元素的长度是否等于i，然后删除第一个元素，再用内循环转译数字凭借字符串，放入集合的尾部，这样可以保证遍历上一次集合的值。
方法二的解题代码：
1 public static ListletterCombinations2(String digits) { 2 LinkedList list = new LinkedList (); 3 if (digits.length() == 0) { 4 return list; 5 } 6 list.add(""); 7 for (int i = 0; i < digits.length(); i++) { 8 int x = Character.getNumericValue(digits.charAt(i)); 9 while (list.peek().length() == i) {10 // 删除集合第一个元素并返回11 String s = list.remove();12 for (char c : dict2(x)) {13 list.add(s + c);14 }15 }16 }17 return list;18 }19 20 // 数字-字母转译字典21 private static char[] dict2(int num) {22 char[] result;23 if (num == 9 || num == 7) {24 result = new char[4];25 } else {26 result = new char[3];27 }28 // 注意7和9代表4个字母29 char start;30 if (num < 8) {31 start = (char) ('a' + (num - 2) * 3);32 } else {33 start = (char) ('a' + (num - 2) * 3 + 1);34 }35 result[0] = start;36 result[1] = (char) (start + 1);37 result[2] = (char) (start + 2);38 if (num == 9 || num == 7) {39 result[3] = (char) (start + 3);40 }41 return result;42 }
备注
相关链接：
PS：如有不正确或提高效率的方法，欢迎留言，谢谢！
转载地址：http://doyyz.baihongyu.com/