Letter Combinations of a Phone Number

Question (LC.17)

Given a string of digits, return all possible letter combinations that the input could represent.

Example

I: "23"
O: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

The recursion is exactly same as subset. We can just use the backtrack template.

Approach

All possible combinations require backtracking, exhaustive search it is.

Step 0 Create a mapping so we can use the for loop to backtrack
Step 1 standard backtrack helper

Code

public List<String> letterCombinations(String digits) {
    List<String> combinations = new ArrayList<>();
    // checking input
    if (digits == null || digits.length() == 0) {
        return combinations;
    }
    // Step 0 create map
    Map<Character, char[]> phoneMap = new HashMap<Character, char[]>();
    phoneMap.put('0', new char[] {});
    phoneMap.put('1', new char[] {});
    phoneMap.put('2', new char[] { 'a', 'b', 'c' });
    phoneMap.put('3', new char[] { 'd', 'e', 'f' });
    phoneMap.put('4', new char[] { 'g', 'h', 'i' });
    phoneMap.put('5', new char[] { 'j', 'k', 'l' });
    phoneMap.put('6', new char[] { 'm', 'n', 'o' });
    phoneMap.put('7', new char[] { 'p', 'q', 'r', 's' });
    phoneMap.put('8', new char[] { 't', 'u', 'v'});
    phoneMap.put('9', new char[] { 'w', 'x', 'y', 'z' });
    // Step 1 backtrack helper
    searchDigits(digits, phoneMap, combinations, new StringBuilder());
    return combinations;
}

private void searchDigits(String digits, 
                          Map<Character, char[]> phoneMap,
                          List<String> combinations,
                          StringBuilder combination) {
    int curPos = combination.length();
    // base case
    if (curPos == digits.length()) {
        combinations.add(combination.toString());
        return;
    }
    // backtrack
    for (char letter : phoneMap.get(digits.charAt(curPos))) {
        combination.append(letter);
        searchDigits(digits, phoneMap, combinations, combination);
        combination.deleteCharAt(combination.length() - 1);
    }
}

Time Complexity

This is exponential time. Let k = number of letter representations per key and n = len(digits). O(k^n).