Free Backtracking lessonsBacktracking · Stage 1 · Combinations · Step 3

Letter combinations of a phone number

Instead of two choices per step, loop over a whole group of letters — one digit, one position. About 8 minutes.

One position, several letters

Old phone keypads print letters on the number keys: 2 has "abc", 3 has "def", and so on up to 9. Seven and nine get four letters: "pqrs" and "wxyz". Type 23 and you could spell any word with a letter from key 2, then a letter from key 3: 3 × 3 = 9 possibilities.

Backtracking builds each one position by position: for the current digit try every letter, go to the next digit, and take the letter back.

One digit, one position: move left to right through the digits, never back.

Loop the group: try each letter of the current key, recurse, then undo.

digits = "23" · 2 → abc, 3 → def

result: []

Position 0 is the digit 2: try each of its letters. First 'a'.

Move 1 of 4

The base case is "ran out of digits"

When you have gone past the last digit, the working list already holds one letter for every position: a finished word. Join it, save it, and return.

An empty input has no positions to fill at all, so the answer is an empty list, not a list holding one empty word. That is an easy edge case to get wrong.

Base case: past the last digit, so join the letters, save, and return.

Empty input, empty output: no digits means no combinations at all.

In code

if not digits:
    return []
keys = {"2": "abc", "3": "def", "4": "ghi",
        "5": "jkl", "6": "mno", "7": "pqrs",
        "8": "tuv", "9": "wxyz"}
res = []
def go(idx, curr):
    if idx == len(digits):
        res.append("".join(curr))
        return
    for ch in keys[digits[idx]]:
        curr.append(ch)
        go(idx + 1, curr)
        curr.pop()
go(0, [])
return res

Quick check

digits = "79" has one digit mapping to 4 letters ("pqrs") and one mapping to 4 letters ("wxyz"). How many letter combinations does that produce?

A16, since it's 4 choices for the first letter times 4 for the second
B8, adding the two groups' sizes together (4 + 4)
C4, the same as either digit's letter count alone

Show the answer

16, since it's 4 choices for the first letter times 4 for the second. Each position's choices multiply independently: 4 × 4 = 16 total combinations.

Your problem

Letter combinations of a phone number

A phone keypad maps each digit 2 through 9 to a group of letters, exactly like an old telephone: 2 → "abc", 3 → "def", 4 → "ghi", 5 → "jkl", 6 → "mno", 7 → "pqrs", 8 → "tuv", 9 → "wxyz". Given a string digits made only of digits 2 through 9, return every letter combination that picks one letter from each digit's group, in the same order as digits. If digits is empty, return an empty list. List the combinations in lexicographic order.

Example

digits = "79" → ["pw", "px", "py", "pz", "qw", "qx", "qy", "qz", "rw", "rx", "ry", "rz", "sw", "sx", "sy", "sz"]

0 ≤ digits.length ≤ 4 · every character in digits is one of '2'-'9'

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.