17. Letter Combinations of a Phone Number

Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Solution

This problem asks us to list all possible strings, so we can think of using backtracking to solve it. When processing each digit, we append the letter corresponding to the digit to the string prefix, and when the last digit is processed, the prefix will be one of the result strings. We can’t use String because we have to keep appending letters to and removing letters from the prefix. If you use String, it will create a new String every time you append or remove letter from String, which is very performance-consuming. We can use StringBuilder instead.

Backtracking

• Time:
• Space:

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> results = new ArrayList<>();
        if (digits == null || digits.length() == 0) return results;

        Map<Character, char[]> map = buildDigitMap();
        dfs(digits, 0, map, new StringBuilder(), results);
        return results;
    }

    private Map<Character, char[]> buildDigitMap() {
        Map<Character, char[]> map = new HashMap<>();
        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'});
        return map;
    }

    private void dfs(String digits, int index, Map<Character, char[]> map, StringBuilder prefix, List<String> results) {
        if (index >= digits.length()) return;

        char c = digits.charAt(index);
        boolean isLast = index == digits.length() - 1;
        char[] letters = map.get(c);
        for (char d : letters) {
            prefix.append(d);
            if (isLast) {
                results.add(prefix.toString());
            } else {
                dfs(digits, index + 1, map, prefix, results);
            }
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }
}

Reference

• 17. Letter Combinations of a Phone Number, LeetCode.
• 17. Letter Combinations of a Phone Number, LeetCode Solutions.