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.

Backtracking problem. Use a map <Integer, char[] > (or list) to store the mapping between numbers and letters. Starts from 0, every time we add one letter to the StringBuilder, its length will increment by 1. So in each recursion, we start the loop at the length of the string builder, which points to the next number in string digits whose mapping is to be added.

public List letterCombinations(String digits) {
        if (digits == null)
            throw new NullPointerException("Null string!");
        List rst = new ArrayList ();
        Map map = new HashMap();
        map.put('0', new char[] {});
        map.put('1', new char[] {});
        map.put('2', new char[] { 'a', 'b', 'c' });
        map.put('3', new char[] { 'd', 'e', 'f' });
        map.put('4', new char[] { 'g', 'h', 'i' });
        map.put('5', new char[] { 'j', 'k', 'l' });
        map.put('6', new char[] { 'm', 'n', 'o' });
        map.put('7', new char[] { 'p', 'q', 'r', 's' });
        map.put('8', new char[] { 't', 'u', 'v'});
        map.put('9', new char[] { 'w', 'x', 'y', 'z' });
        getLetter(digits, map, rst, new StringBuilder ());
        return rst;
    }
    private void getLetter(String digits, Map map, List rst, StringBuilder sb) {
        if (sb.length() == digits.length()) {
            rst.add(sb.toString());
            return;
        }
        for (char c : map.get(digits.charAt(sb.length()))) {
            sb.append(c);
            getLetter(digits, map, rst, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }