[LeetCode] Letter Combinations of a Phone Number

Problem:

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.

Solution:O(n)

public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        Map<Character, String> map = new HashMap<>();
        map.put('1', "");
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        
        char[] set = new char[digits.length()];
        ArrayList<String> ret = new ArrayList<String>();
        getDigits(digits, 0, set, ret,map);
        return ret;
    }
    
    public void getDigits(String digits, int i, char[] set, ArrayList<String> ret,Map<Character, String> map){
        if(i == digits.length()){
            ret.add(new String(set));
            return;
        }
        String letters = map.get(digits.charAt(i));
        for(int j = 0; j < letters.length(); j++){
            set[i] = letters.charAt(j);
            getDigits(digits, i + 1, set, ret,map);
        }
    }
}