Letter Combinations Phone

Problem

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent on a phone keypad.

Approach

Recursive backtracking: map each digit to its letters, build combinations one digit at a time. At each level pick one letter for the current digit, then recurse on remaining digits.

When to Use

Cartesian product generation, combinatorial enumeration. Similar structure to permutations but across different character sets.

Complexity

Time	O(4^n) — where n = number of digits (worst case: 7 and 9 have 4 letters)
Space	O(n) — recursion depth (excluding output)

Implementation

SolutionTestsChallenge

letter_combinations_phone

Letter Combinations of a Phone Number — digit-to-letter mapping.

Problem

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent on a phone keypad.

Approach

Recursive backtracking: map each digit to its letters, build combinations one digit at a time. At each level pick one letter for the current digit, then recurse on remaining digits.

When to use

Cartesian product generation, combinatorial enumeration. Similar structure to permutations but across different character sets.

Complexity

Time: O(4^n) — where n = number of digits (worst case: 7 and 9 have 4 letters) Space: O(n) — recursion depth (excluding output)

letter_combinations

letter_combinations(digits: str) -> list[str]

Return all letter combinations for the given phone digits.

letter_combinations("23") ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'] letter_combinations("") []

Source code in src/algo/recursion/letter_combinations_phone.py

def letter_combinations(digits: str) -> list[str]:
    """Return all letter combinations for the given phone *digits*.

    >>> letter_combinations("23")
    ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
    >>> letter_combinations("")
    []
    """
    if not digits:
        return []

    result: list[str] = []

    def backtrack(index: int, current: list[str]) -> None:
        if index == len(digits):
            result.append("".join(current))
            return
        for letter in DIGIT_TO_LETTERS[digits[index]]:
            current.append(letter)
            backtrack(index + 1, current)
            current.pop()

    backtrack(0, [])
    return result

tests/recursion/test_letter_combinations_phone.py

"""Tests for the letter combinations of a phone number problem."""

import math

from hypothesis import given
from hypothesis import strategies as st

from algo.recursion.letter_combinations_phone import (
    DIGIT_TO_LETTERS,
    letter_combinations,
)


class TestLetterCombinations:
    def test_two_digits(self) -> None:
        result = letter_combinations("23")
        assert result == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

    def test_single_digit(self) -> None:
        assert letter_combinations("2") == ["a", "b", "c"]

    def test_empty_string(self) -> None:
        assert letter_combinations("") == []

    def test_digit_with_four_letters(self) -> None:
        result = letter_combinations("7")
        assert result == ["p", "q", "r", "s"]

    def test_three_digits(self) -> None:
        result = letter_combinations("234")
        assert len(result) == 3 * 3 * 3  # 27
        assert result[0] == "adg"
        assert result[-1] == "cfi"

    @given(
        digits=st.text(
            alphabet=st.sampled_from("23456789"),
            min_size=1,
            max_size=4,
        ),
    )
    def test_result_count_is_product_of_letter_counts(self, digits: str) -> None:
        result = letter_combinations(digits)
        expected_count = math.prod(len(DIGIT_TO_LETTERS[d]) for d in digits)
        assert len(result) == expected_count
        # All results have correct length
        for combo in result:
            assert len(combo) == len(digits)
        # No duplicates
        assert len(result) == len(set(result))

Implement it yourself

Run: just challenge recursion letter_combinations_phone

Then implement the functions to make all tests pass. Use just study recursion for watch mode.

Reveal Solution

letter_combinations_phone

Letter Combinations of a Phone Number — digit-to-letter mapping.

Problem

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent on a phone keypad.

Approach

Recursive backtracking: map each digit to its letters, build combinations one digit at a time. At each level pick one letter for the current digit, then recurse on remaining digits.

When to use

Cartesian product generation, combinatorial enumeration. Similar structure to permutations but across different character sets.

Complexity

Time: O(4^n) — where n = number of digits (worst case: 7 and 9 have 4 letters) Space: O(n) — recursion depth (excluding output)

letter_combinations

letter_combinations(digits: str) -> list[str]

Return all letter combinations for the given phone digits.

letter_combinations("23") ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'] letter_combinations("") []

Source code in src/algo/recursion/letter_combinations_phone.py

def letter_combinations(digits: str) -> list[str]:
    """Return all letter combinations for the given phone *digits*.

    >>> letter_combinations("23")
    ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
    >>> letter_combinations("")
    []
    """
    if not digits:
        return []

    result: list[str] = []

    def backtrack(index: int, current: list[str]) -> None:
        if index == len(digits):
            result.append("".join(current))
            return
        for letter in DIGIT_TO_LETTERS[digits[index]]:
            current.append(letter)
            backtrack(index + 1, current)
            current.pop()

    backtrack(0, [])
    return result