No.017:Letter Combinations of a Phone Number

时间:2024-06-30 00:02:50

问题:

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.

No.017:Letter Combinations of a Phone Number

官方难度:

Medium

翻译:

给定一个数字组成的字符串,返回所有可能的字母集合。数字和字母的映射关系就像电话上显示的一样。

例子:

输入字符串:"23"

输出集合:["ad","ae","af","bd","be","bf","cd","ce","cf"]

集合内的元素顺序没有规定。

方法一:

  1. 首先需要定义一个数值-字符的字典转译方法,使用长度为8的字符串数组,存放a-z的字母,然后根据输入的int值,返回一个char[]类型数组。
  2. 输入数字字符长度为0时,返回的是一个空的集合,而不是长度为1,包含一个空字符串的集合,需要特殊处理。
  3. 先将空字符串放入集合,然后开启递归。
  4. 递归终点是数字字符串长度为0,返回集合。
  5. 每次遍历集合的所有元素,根据数字字符串的第一个数字,排除所有可能性,将结果放回入参的集合,作为下一次递归的入参。
  6. 截取数字字符串的第一个数字的方法是:targetDigit.charAt(0)-‘a’。
  7. 注意入参检查

方法一的解题代码:

 public static List<String> letterCombinations(String digits) {
if (digits == null) {
throw new IllegalArgumentException("Input error");
}
String copyDigits = digits;
while (copyDigits.length() > 0) {
int i = copyDigits.charAt(0) - '0';
if (i < 2 || i > 9) {
throw new IllegalArgumentException("Input error");
}
copyDigits = copyDigits.substring(1);
}
// 只接受2-9的数值字符串
List<String> source = new LinkedList<>();
if (digits.equals("")) {
return source;
}
// 初始size需要等于1,不然之后不能循环
source.add("");
return format(source, digits);
} // 递归方法
private static List<String> format(List<String> source, String targetDigit) {
if (targetDigit.length() == 0) {
return source;
}
List<String> result = new LinkedList<>();
// 第一个数
int first = targetDigit.charAt(0) - '0';
char[] cArray = dict(first);
// source集合和targetDigit第一个数字对应字典的全排列
for (String str : source) {
for (char c : cArray) {
result.add(str + c);
}
}
// 将target转成source,继续递归
return format(result, targetDigit.substring(1));
} private static char[] dict(int num) {
String[] mappping = new String[] { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
return mappping[num - 2].toCharArray();
}

letterCombinations

方法二:

1.  转译字典还能使用其他方法实现,不使用字符串数组,获得返回的char型数组的第一个值,然后依次添加。

2.  有一个隐藏的性质,得到的每一个字母字符串长度,与最初的数字字符串长度是一样的。然后指定声明集合为LinkedList,利用LinkedList.remove()方法删除并返回第一个元素,以及LinkedList.peek()方法得到集合的第一个元素。

3.  利用三次循环,外循环获取对应数字,除了方法一中的办法,还可以使用Character包装类自带的方法:Character.getNumbericValue()。

4.  中循环,使用while()循环判断集合的第一个元素的长度是否等于i,然后删除第一个元素,再用内循环转译数字凭借字符串,放入集合的尾部,这样可以保证遍历上一次集合的值。

方法二的解题代码:

     public static List<String> letterCombinations2(String digits) {
LinkedList<String> list = new LinkedList<String>();
if (digits.length() == 0) {
return list;
}
list.add("");
for (int i = 0; i < digits.length(); i++) {
int x = Character.getNumericValue(digits.charAt(i));
while (list.peek().length() == i) {
// 删除集合第一个元素并返回
String s = list.remove();
for (char c : dict2(x)) {
list.add(s + c);
}
}
}
return list;
} // 数字-字母转译字典
private static char[] dict2(int num) {
char[] result;
if (num == 9 || num == 7) {
result = new char[4];
} else {
result = new char[3];
}
// 注意7和9代表4个字母
char start;
if (num < 8) {
start = (char) ('a' + (num - 2) * 3);
} else {
start = (char) ('a' + (num - 2) * 3 + 1);
}
result[0] = start;
result[1] = (char) (start + 1);
result[2] = (char) (start + 2);
if (num == 9 || num == 7) {
result[3] = (char) (start + 3);
}
return result;
}

letterCombinations2

备注

  1. 就效率而言,两个方法是相同的,并没有高下之分。方法一的用法更加便于理解,但是其中使用了递归,所以在空间利用上要明显劣于方法二。推荐使用方法二。

相关链接:

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q017.java

PS:如有不正确或提高效率的方法,欢迎留言,谢谢!