首页 > 代码库 > No.017：Letter Combinations of a Phone Number

No.017：Letter Combinations of a Phone Number

2024-08-16 22:18:07   221人阅读

题目：

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


联系
我们