Letter Combinations of a Phone Number

Given a string of digits from 2–9, return every letter combination the digits could map to on a telephone keypad, in any order. With n digits, each contributing up to 4 letters, the output size is up to 4ⁿ — the machine must build all of them.

The key insight: this is a Cartesian product built one position at a time. At each digit, the current partial combinations each branch into the digit's letters. Iterative accumulation does this without recursion frames: start with the empty prefix, then for each digit, replace every existing prefix with all its extensions.

Approach:

1. Map each digit to its letters; handle the empty input upfront.
2. Start with [""] and fold over the digits.
3. For each digit, extend every current combination with each possible letter.

def letter_combinations(digits):
    mapping = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
    }
    if not digits:
        return []
    result = [""]
    for digit in digits:
        result = [prefix + letter for prefix in result for letter in mapping[digit]]
    return result

Time: O(4ⁿ·n). Space: O(4ⁿ) for the output.

Trickiest edge case: the empty string — the result must be [], not [""]; that is the one case where the product of zero factors is not the single empty combination.