首页 > 代码库 > 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     }
View Code

测试代码地址:

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