Letter Combinations of a Phone Number – Solution & Complexity

Q: What is the time and space complexity of Letter Combinations of a Phone Number?

The optimal Letter Combinations of a Phone Number solution runs in `O(4^n)` time and `O(n)` space. Backtrack through the digit-to-letters mapping, building each combination one digit at a time.

Q: What is the most efficient way to solve Letter Combinations of a Phone Number?

Backtrack through the digit-to-letters mapping, building each combination one digit at a time. This gives `O(4^n)` time complexity, and is a classic strings and backtracking problem.

Q: How do you solve Letter Combinations of a Phone Number in Python & JavaScript?

We provide a worked Letter Combinations of a Phone Number solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Letter Combinations of a Phone Number an easy or hard interview question?

Letter Combinations of a Phone Number is generally rated **Medium**. It tests strings and backtracking, which are common coding-interview patterns.

1. Understand the Search Space

Each digit maps to a small group of letters, like 2 -> abc and 3 -> def.
A valid answer chooses exactly one letter for every digit.
If digits is empty, there are no combinations to build, so return an empty list.

2. Start with Incremental Building

Keep a list of partial combinations seen so far.
For the next digit, append each possible letter to each partial combination.
This works, but recursion or backtracking expresses the choice process more directly.

def letter_combinations(digits):
    combinations = [""]
    for digit in digits:
        next_combinations = []
        for prefix in combinations:
            for letter in phone[digit]:
                next_combinations.append(prefix + letter)
        combinations = next_combinations
    return combinations

3. Use Backtracking

Backtracking builds one candidate combination at a time.
At position i, choose one letter for digits[i], recurse to the next position, then try the next letter.
When the candidate length equals the input length, it is complete.

def backtrack(index, path):
    if index == len(digits):
        result.append("".join(path))
        return

    for letter in phone[digits[index]]:
        path.append(letter)
        backtrack(index + 1, path)
        path.pop()

4. Preserve the Required Order

Iterate through digits from left to right.
Iterate through each mapped letter in the normal phone keypad order.
This naturally produces results like ad, ae, af, bd, ... for 23.

5. Complete Solution and Complexity

The final solution handles the empty input first, then backtracks through every possible letter choice.
If there are n digits and each has up to 4 letters, time complexity is O(4^n * n) including string creation.
Space complexity is O(n) for the recursion path, plus the output list.

def letter_combinations(digits: str) -> list[str]:
    if not digits:
        return []

    phone = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }
    result = []

    def backtrack(index, path):
        if index == len(digits):
            result.append("".join(path))
            return

        for letter in phone[digits[index]]:
            path.append(letter)
            backtrack(index + 1, path)
            path.pop()

    backtrack(0, [])
    return result

Letter Combinations of a Phone Number – Solution & Complexity

1. Understand the Search Space

2. Start with Incremental Building

3. Use Backtracking

4. Preserve the Required Order

5. Complete Solution and Complexity

FAQ

What is the time and space complexity of Letter Combinations of a Phone Number?

What is the most efficient way to solve Letter Combinations of a Phone Number?

How do you solve Letter Combinations of a Phone Number in Python & JavaScript?

Is Letter Combinations of a Phone Number an easy or hard interview question?