LeetCode. 17. Letter Combinations of a Phone Number

Problem

Backtracking

The input contains digits from 2 through 9. Each digit maps directly to its phone-keypad letters. If the input is empty, there are no combinations, so return an empty list.

The recursion processes one digit at a time. Its invariant is that, upon entering the call for index i, the StringBuilder contains exactly one selected letter for each of the first i digits, in order. For each letter mapped to the current digit, append that letter, recurse to the next index, and then delete the appended character before trying the next letter. At depth N, the prefix contains one letter per input digit, so save it as a completed combination.

There are at most 4^N combinations, and copying each completed string takes O(N) time, giving output-sensitive worst-case time O(N * 4^N). The builder and recursion stack use O(N) auxiliary space, excluding the output list.

Java

class Solution {
    private static final String[] KEYPAD = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> answer = new ArrayList<>();
        if (digits.isEmpty()) {
            return answer;
        }

        backtrack(digits, 0, new StringBuilder(), answer);
        return answer;
    }

    private void backtrack(String digits, int index, StringBuilder prefix, List<String> answer) {
        if (index == digits.length()) {
            answer.add(prefix.toString());
            return;
        }

        String letters = KEYPAD[digits.charAt(index) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            prefix.append(letters.charAt(i));
            backtrack(digits, index + 1, prefix, answer);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }
}