首页 > 代码库 > No.017:Letter Combinations of a Phone Number
No.017:Letter Combinations of a Phone Number
题目:
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. 需要一个数字-字母的转译字典方法。
2. 整个组合的过程,可以使用递归来实现。
3. 递归的方法,拥有两个入参,第一个入参是一个List<String>类型的source,代表着已经排列好的数字所代表的字符串集合;第二个入参是一个String类型的targetDigit,代表下一个即将遇到的数字。当targetDigit为null,或者长度小于1,表示递归的终点。
4. 从第一个数字开始,列出所有的字母组合的可能集合,当遇到下一个数字时,遍历这个集合,将第二个数字可能代表的字母组合append(),组成新的代表前2个数字代表的字母集合,作为以一次递归的第一个入,参依次类推。
解题中可能遇到的困难:
1. 字典方法,注意7、9的特殊情况,分别是1-4的映射关系。
2. 第一次进入方法是,第一个参数source不是单纯的new ArrayList<>(),应该在集合中加一个空字符串"",不然之后的运行过程中,size()会一直等于0,因为循环append()是在source的基础上增加的,source.size()为0,就不会进入循环了。
3. 在append()之后,注意内循环一次结束之后,将结果集StringBuffer还原。
解题代码:
1 private static List<String> method(String digit) { 2 // 入参检查省略 3 // source一开始没有值 4 List<String> source = new ArrayList<>(); 5 // 初始size需要等于1,不然之后不能循环 6 source.add(""); 7 return format(source, digit); 8 } 9 10 private static List<String> format(List<String> source, String targetDigit) { 11 // 剩余数字不存在,返回source 12 if (targetDigit == null || targetDigit.length() < 1) { 13 return source; 14 } 15 List<String> result = new ArrayList<>(); 16 // 截取剩余未处理字符串的第一个值 17 int firstNumber; 18 try { 19 firstNumber = Integer.valueOf(targetDigit.substring(0, 1)); 20 } catch (NumberFormatException e) { 21 return null; 22 } 23 // 获取对应数字的字典 24 List<Character> cList = dict(firstNumber); 25 if (cList == null) { 26 return null; 27 } 28 // source集合和targetDigit第一个数字对应字典的全排列 29 for (String str : source) { 30 StringBuffer sb = new StringBuffer(str); 31 for (Character c : cList) { 32 sb.append(c); 33 result.add(sb.toString()); 34 // 注意还原StringBuffer 35 sb = new StringBuffer(str); 36 } 37 } 38 // 将target转成source,继续递归 39 return format(result, targetDigit.substring(1)); 40 } 41 42 // 数字-字母转译字典 43 private static List<Character> dict(int number) { 44 // 不接收2-9以外的数字 45 if (number < 2 || number > 9) { 46 return null; 47 } 48 List<Character> list = new ArrayList<>(); 49 // 注意7和9代表4个字母 50 char start; 51 if (number < 8) { 52 start = (char) (‘a‘ + (number - 2) * 3); 53 } else { 54 start = (char) (‘a‘ + (number - 2) * 3 + 1); 55 } 56 list.add(start); 57 list.add((char) (start + 1)); 58 list.add((char) (start + 2)); 59 if (number == 9 || number == 7) { 60 list.add((char) (start + 3)); 61 } 62 return list; 63 }
测试代码地址:
https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q017.java
LeetCode题目地址:
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
PS:如有不正确或提高效率的方法,欢迎留言,谢谢!
No.017:Letter Combinations of a Phone Number