{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Letter Combinations of a Phone Number – Solution & Complexity

Interview solutions
/
Letter Combinations of a Phone Number

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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

FAQ

See also

Practice Letter Combinations of a Phone Number online (run code in the browser)Generate Parentheses solution (medium)Palindrome Partitioning solution (medium)Alien Dictionary solution (hard)Combination Sum solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?