No.017：Letter Combinations of a Phone Number-白红宇的个人博客

No.017：Letter Combinations of a Phone Number

发布日期：2021-05-09 03:58:58 浏览次数：9 分类：博客文章

本文共 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"]

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

方法一：

首先需要定义一个数值-字符的字典转译方法，使用长度为8的字符串数组，存放a-z的字母，然后根据输入的int值，返回一个char[]类型数组。

输入数字字符长度为0时，返回的是一个空的集合，而不是长度为1，包含一个空字符串的集合，需要特殊处理。

先将空字符串放入集合，然后开启递归。

递归终点是数字字符串长度为0，返回集合。

每次遍历集合的所有元素，根据数字字符串的第一个数字，排除所有可能性，将结果放回入参的集合，作为下一次递归的入参。

截取数字字符串的第一个数字的方法是：targetDigit.charAt(0)-‘a’。

注意入参检查

方法一的解题代码：

1 public static List
     
       letterCombinations(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     }

letterCombinations

方法二：

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

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

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

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

方法二的解题代码：

1     public static List
     
       letterCombinations2(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     }

letterCombinations2

备注

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

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章