DSA Letter Combinations of a Phone Number

The problem

Letter Combinations asks for every string a phone keypad can spell from a string of digits. Each digit from 2 to 9 stands for a fixed row of letters. A combination picks exactly one letter for each digit, in digit order.

cases = [
    ("2", ["a", "b", "c"]),
    ("23", ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]),
    ("7", ["p", "q", "r", "s"]),
    ("", []),
]
for digits, expected in cases:
    print("digits", repr(digits), "combinations:", expected)

Two digits give nine combinations, not six. Each letter of the first digit pairs with every letter of the second digit. The row sizes multiply, and three times three is nine.

Intuition: nested loops work until the digit count moves

The first idea reaches for nested loops, one loop per digit. Two loops handle two digits well. The output below is correct and complete for the digits 23.

KEYS = {"2": "abc", "3": "def"}
result = []
for first in KEYS["2"]:
    for second in KEYS["3"]:
        result.append(first + second)
print(result)
print("count:", len(result))

The idea breaks when the digit count is not known in advance. Written code cannot grow a new loop for each new input. A third digit has no loop waiting for it, so the method needs a shape that fits any digit count.

Brute force: every alphabet string, then filter

The brute force builds every string of the right length over the full alphabet. It keeps a string only when each letter sits in the row of its digit. A counter records the strings built.

KEYS = {"2": "abc", "3": "def"}
def combinations_brute(digits):
    results = []
    path = []
    built = [0]
    def search(index):
        if index == len(digits):
            built[0] += 1
            text = "".join(path)
            if all(text[i] in KEYS[digits[i]] for i in range(len(digits))):
                results.append(text)
            return
        for letter in "abcdefghijklmnopqrstuvwxyz":
            path.append(letter)
            search(index + 1)
            path.pop()
    search(0)
    return results, built[0]

result, built = combinations_brute("23")
print(result)
print("combinations kept:", len(result))
print("alphabet strings built:", built)

The brute force built 676 alphabet strings to keep 9 combinations. The waste is every letter that no digit in the input can produce. The optimal search never places those letters at all.

The optimal solution: one digit position at a time

The state is the path of letters chosen so far plus the index of the digit now being answered, and the search tries only the letters in that digit's row before moving to the next digit. That one sentence is the whole method.

Backtracking replaces the nested loops. The recursion depth follows the digit count, whatever it is. No loop count is fixed in advance, and no letter outside a digit's row is ever placed.

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

def combinations(digits):
    if digits == "":
        return []
    if any(digit not in KEYS for digit in digits):
        return []
    results = []
    path = []
    def search(index):
        if index == len(digits):
            results.append("".join(path))
            return
        for letter in KEYS[digits[index]]:
            path.append(letter)
            search(index + 1)
            path.pop()
    search(0)
    return results

cases = [
    ("2", ["a", "b", "c"]),
    ("23", ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]),
    ("7", ["p", "q", "r", "s"]),
    ("", []),
]
for digits, expected in cases:
    result = combinations(digits)
    print("digits", repr(digits), "->", result, "match:", result == expected)

Every case matches. The empty input returns an empty list. There is no digit to answer, so there is no combination to build.

Walkthrough: the digits 23, letter by letter

The walk prints each placement and each finished combination. The first digit changes slowest. All three letters of the second digit run before the first digit advances.

KEYS = {"2": "abc", "3": "def"}
digits = "23"
path = []
def search(index):
    if index == len(digits):
        print("record", "".join(path))
        return
    for letter in KEYS[digits[index]]:
        path.append(letter)
        print("place", letter, "for digit", digits[index], "- path:", "".join(path))
        search(index + 1)
        path.pop()
search(0)

Count the records. There are nine, one per pairing of the two rows. The a branch finishes fully before the b branch starts, which fixes the printed order.

Complexity

Time is O(n times 4^n) in the worst case, where n is the digit count and 4 is the longest row length. The combination count is the product of the row sizes, and copying each combination costs n letters.

Extra space is O(n) besides the stored results. The path holds one letter per digit, and nothing else grows with the input.

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

for digits in ("2", "23", "234", "2345"):
    count = 1
    for digit in digits:
        count *= len(KEYS[digit])
    print("digits", digits, "- combinations:", count, "- alphabet strings:", 26 ** len(digits))

The gap widens with every digit. The brute force pays for the whole alphabet at each position. The backtracking search pays only for the letters the keypad actually offers.

Edge cases and pitfalls

Digits 0 and 1 carry no letters on the keypad. This article's function returns an empty list when a digit has no row, instead of failing on a missing entry. The empty digit string returns an empty list for the same reason.

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

def combinations(digits):
    if digits == "":
        return []
    if any(digit not in KEYS for digit in digits):
        return []
    results = []
    path = []
    def search(index):
        if index == len(digits):
            results.append("".join(path))
            return
        for letter in KEYS[digits[index]]:
            path.append(letter)
            search(index + 1)
            path.pop()
    search(0)
    return results

print("empty digits:", combinations(""))
print("digit 9 alone:", combinations("9"))
print("digit with no row:", combinations("21"))
print("one ordinary digit:", combinations("2"))

The classic pitfall in this problem is adding the row sizes instead of multiplying them. Two rows of three letters give nine combinations, not six. The walkthrough records prove the product, one printed combination at a time.