LeetCode 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

Total Accepted: 130635
Total Submissions: 395653
Difficulty: Medium
Contributors: Admin

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.

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.

【题目分析】

给定一个手机键盘，键盘中的数字对应若干个字母。给定一个数字序列，返回这些数字对应的字母所能成的所有字符串。

【思路】

1. 用回溯的角度来解决这道题的话，其实是比较简单的。每一步的解空间就是当前遍历到的数字对应的字母。

2. discuss里面有用队列来做的。

【java代码】

 1 public class Solution {
 2     public List<String> letterCombinations(String digits) {
 3         List<String> res = new ArrayList<>();
 4         if(digits == null || digits.length() == 0) return res;
 5         //查看数字串中是否存在1和0
 6         if(digits.indexOf("0") != -1 || digits.indexOf("1") != -1) return res;
 7         
 8         char[][] letters = {{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},
 9                            {'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
10         
11         char[] digit = digits.toCharArray();
12         
13         combination(res, new StringBuilder(), digit, letters, 0);
14         
15         return res;
16     }
17     
18     public void combination(List<String> res, StringBuilder sb, char[] digit, char[][] letters, int start) {
19         if(sb.length() == digit.length) {
20             res.add(sb.toString());
21             return;
22         }
23         char[] curletters = letters[digit[start]-50];
24         for(char ch : curletters) {
25             sb.append(ch);
26             combination(res, sb, digit, letters, start+1);
27             sb.deleteCharAt(sb.length()-1);
28         }
29     }
30 }

LeetCode 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

相关推荐