2015年9月17日星期四

Leetcode 17 Letter Combinations of a Phone Number

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.
Solution 1: Use dfs, use StringBuilder and char array could save some time. Pay attention, blank string "" should not be added to result.
 public class Solution {  
   String[] dict={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};  
   public List<String> letterCombinations(String digits) {  
     char[] dig=digits.toCharArray();  
     List<String> res=new ArrayList<>();  
     StringBuilder one=new StringBuilder();  
     dfs(dig,0,one,res);  
     return res;  
   }  
   private void dfs(char[] dig, int d, StringBuilder one, List<String> res) {  
     if (d==dig.length) {  
       if (d>0) res.add(one.toString()); //blank String "" should not be added  
     }  
     else {  
       int index=dig[d]-'0';  
       for (int i=0; i<dict[index].length(); i++) {  
         char c=dict[index].charAt(i);  
         one.append(c);  
         dfs(dig,d+1,one,res);  
         one.deleteCharAt(one.length()-1);  
       }  
     }  
   }  
 }  

没有评论:

发表评论