Letter Combination 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.

Hint: the first question is, how do we store and find the letters that can be represented by a digit? Using hashtable!

The second question, how can we enumerate all combinations? For example, the imput String is "23". Look at digit 2, we could have this position be a or b or c. 

a
b
c

Then we come to digit 3, we can have it as d, e, f. What we should do? We should append the letter after the previous position which we have already solved. Right?

ad
ae
af
bd
be
bf
...

Therefore, we should enumerate the letters at the current digit repeatedly, put one to the current position, then we call the same function recursively at the next position.

01 public ArrayList<String> letterCombinations(String digits) {
02     char [] input=digits.toCharArray();
03     ArrayList<String> results=new ArrayList<String>();
04     char [] output=new char[input.length];
05 
06   //use a hashtable to map the keyboard to the letters
07     Hashtable<Character,String> ht=new Hashtable<Character,String>();
08     ht.put('2',"abc");
09     ht.put('3',"def");
10     ht.put('4',"ghi");
11     ht.put('5',"jkl");
12     ht.put('6',"mno");
13     ht.put('7',"pqrs");
14     ht.put('8',"tuv");
15     ht.put('9',"wxyz");
16     doCombine(ht, 0, input, output, results);
17     return results;
18 }
19 
20 public void doCombine(Hashtable<Character,String>ht, int pos, char [] input, char[] output, ArrayList<String> results)
21 {
22   //reach the last index, then output
23     if(pos==input.length)
24     {
25         String outStr=new String(output);
26         results.add(outStr);
27         return;
28     }
29   
30     char c=input[pos];
31     if(!ht.containsKey(c))
32     {
33         return;
34     }
35     String str=ht.get(c);
36     char [] c_str=str.toCharArray();
37   //repeatedly assign all letters that can be represented by the current digit
38     for(int i=0;i<c_str.length;i++)
39     {
40         output[pos]=c_str[i];
41     
42       //call the function recursively to the next digit
43         doCombine(ht,pos+1,input,output,results);
44     }
45 }