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.

 1 public class Solution {
 2     String[] c={    "",
 3                     "",
 4                     "abc",
 5                     "def",
 6                     "ghi",
 7                     "jkl",
 8                     "mno",
 9                     "pqrs",
10                     "tuv",
11                     "wxyz"  };
12     public List<String> letterCombinations(String digits) {
13         ArrayList<String> result = new ArrayList<String>();
14         search(digits, 0, new StringBuilder(), result);
15         return result;
16     }
17     
18     public void search(String dig, int index, StringBuilder sb, ArrayList<String> result){
19         if(index == dig.length()){
20             result.add(sb.toString());
21             return;
22         }
23         int num = dig.charAt(index) - '0';
24         for(int i = 0; i < c[num].length(); i ++){
25             StringBuilder sbs = new StringBuilder(sb);
26             sbs.append(c[num].charAt(i));
27             search(dig, index + 1, sbs, result);
28         }
29     }
30 }