Tuesday, July 8, 2014

Letter Combinations of Phone Number

There are 2 solutions the first one is wrong, the second one is right. Be careful!

 public class Solution {  
   public List<String> letterCombinations(String digits) {  
     List<String> r = new ArrayList<String>();  
     if (digits.length() == 0 || digits == null) return r;  
     String[] table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     helper(digits, r, table, new StringBuilder(), 0, digits.length());  
     return r;  
   }  
   public void helper(String digits, List<String> r, String[] table, StringBuilder temp, int pos, int n) {  
     if (pos >= n) {  
       String s = temp.toString();  
       r.add(s);  
       return;  
     }  
     for (int i=pos; i<n; i++) {  
       int curr = digits.charAt(i)-'0';  
       if (curr == 0 || curr == 1 || digits.charAt(i) == '*' || digits.charAt(i) == '#')  
         helper(digits, r, table, temp, i+1, n);  
       else {  
         String choice = table[curr];  
         for (int j=0; j<choice.length(); j++) {  
           char choiceCurr = choice.charAt(j);  
           temp.append(choiceCurr);  
           helper(digits, r, table, temp, i+1, n);  
           temp = new StringBuilder(temp.substring(0, temp.length()-1));  
         }  
       }  
     }  
   }  
 }  



 public class Solution {  
   public static List<String> letterCombinations(String digits) {  
     List<String> r = new ArrayList<String>();  
     if (digits == null) return r;  
     String[] table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     if (digits.isEmpty()) {  
       r.add("");  
       return r;  
     }  
     helper(digits, r, table, new StringBuilder(), 0, digits.length());  
     return r;  
   }  
   public static void helper(String digits, List<String> r, String[] table, StringBuilder temp, int pos, int n) {  
     if (pos >= n) {  
       String s = temp.toString();  
       r.add(s);  
       return;  
     }  
     int curr = digits.charAt(pos)-'0';  
     if (curr == 0 || curr == 1 || digits.charAt(pos) == '*' || digits.charAt(pos) == '#')  
       helper(digits, r, table, temp, pos+1, n);  
     else {  
       String choice = table[curr];  
       for (int j=0; j<choice.length(); j++) {  
         char choiceCurr = choice.charAt(j);  
         temp.append(choiceCurr);  
         helper(digits, r, table, temp, pos+1, n);  
         temp.deleteCharAt(pos);  
       }  
     }  
   }  
 }  

No comments:

Post a Comment