Search This Blog

Tuesday, December 18, 2012

LeetCode:Letter Combinations of a Phone Number

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.

public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> res = new ArrayList<String> ();
        res.add("");
        if(digits==null) return res;
        String[] table = digitToString();
        for(int i=0;i<digits.length();i++){
            ArrayList<String> cur = new ArrayList<String>();
            char c = digits.charAt(i);
            if(c>='2' && c<='9'){
                for(String temp:res){
                    for(int j=0;j<table[c-'2'].length();j++){
                        cur.add(temp + table[c-'2'].charAt(j));
                    }
                }
            }
            res= new ArrayList<String>(cur);
        }
        return res;    
    }
    public String[] digitToString(){
      String[] res = new String[8];
      char start = 'a';
      
      for(int i=0;i<8;i++){
        int count = (i==5||i==7)?4:3;
        StringBuilder temp = new StringBuilder("");
        for(int j=0;j<count;j++){
            temp.append((char)(start+j));
        }
        start=(char)(start+count);
        res[i] = temp.toString(); 
      }
      return res;
    }
}

2 comments:

Joyce said...

Thank you for this post!
BTW, I guess u might forgot to remove the 'last = c;'.

Xun said...

@Joyce, yes, u r right!