Sweaty Imposter

Letter Combinations of a Phone Number

MediumSubsets (BFS-style generation)NeetCode 150MidOpen on LeetCodeUpdated

You're given a string digits made of the characters 2 to 9. Each digit stands for letters as on a phone keypad: 2 is abc, 3 def, 4 ghi, 5 jkl, 6 mno, 7 pqrs, 8 tuv and 9 wxyz. Return every string you can form by picking one letter per digit, keeping the digits' order. The strings can come in any order. If digits is empty, return an empty list, not a list holding an empty string.

Examples

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

2 maps to a, b, c and 3 maps to d, e, f. Each of the 3 first letters pairs with each of the 3 second letters, giving 9 strings.

digits = "" returns []

There are no digits to pick letters for, so the answer is an empty list.

Constraints

  • 0 <= digits.length <= 4
  • digits[i] in '2'-'9'

Hints

Hint 1

Each digit multiplies the number of strings by however many letters it maps to, how would you build them up?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Build strings one digit at a time: at position idx, try each letter that digits[idx] maps to, append it to the current path, recurse to idx + 1, then remove it. When idx reaches the end, the path is a full combination, so save it. There are at most 4^n combinations (7 and 9 map to four letters) and each takes O(n) to copy out, so time is O(n * 4^n), with O(n) extra space besides the output.

Time

O(n * 4^n)

Space

O(n)

Pitfall

Skipping the empty-input check: with no digits the recursion reaches the end at once and returns [""] instead of []. Also 7 and 9 map to four letters, so a fixed three-letter assumption misses combinations.

Solutions

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

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result;
        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    private void backtrack(String digits, int idx, StringBuilder path, List<String> result) {
        if (idx == digits.length()) {
            result.add(path.toString());
            return;
        }
        for (char c : MAP[digits.charAt(idx) - '0'].toCharArray()) {
            path.append(c);
            backtrack(digits, idx + 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
Drill This