首页 > 代码库 > 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

2024-09-03 22:10:33   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.

技术分享

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 public class Solution {
 2     public List<String> letterCombinations(String digits) {
 3         LinkedList<String> res = new LinkedList<String>();
 4         if(digits.length()==0) return res;
 5         String[] words = new String[]{"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
 6         res.add("");
 7         for(int i=0;i<digits.length();i++){
 8             int num = Character.getNumericValue(digits.charAt(i));
 9             while(res.peek().length()==i){
10                 String s = res.remove();
11                 for(char c:words[num].toCharArray()){
12                     res.add(s+c);
13                 }
14             }
15         }
16         return res;
17     }
18 }

 本题可以用比较客观的方法来解决，回溯法。因为这个是解决一个问题的所有解或者任意一个解，剪枝函数是要在给定的数字字符上选择。回溯的内容自然便是所有字符串的可能性，且使用的是dfs的方法。本题就是从空的字符串一点一点往上加，直到长度和digits的长度一样为止。记住，回溯法要有终止条件。代码如下：

 1 public class Solution {
 2     public List<String> letterCombinations(String digits) {
 3         List<String> res = new LinkedList<String>();
 4         if(digits.length()==0) return res;
 5         String[] words = new String[]{"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
 6         backtracking("",res,digits,words,0);
 7         return res;
 8     }
 9     public void backtracking(String s,List<String> res,String digits,String[] words,int cur){
10         if(cur==digits.length()){
11             res.add(s);
12         }else{
13             String word = words[digits.charAt(cur)-‘0‘];
14             for(int i=0;i<word.length();i++){
15                 backtracking(s+word.charAt(i),res,digits,words,cur+1);
16             }
17         }
18     }
19 }

 

17. Letter Combinations of a Phone Number


联系
我们