LeetCode #17 Medium

Letter Combinations of a Phone Number

Given a string of digits 2-9, return every letter combination the number could spell on an old phone keypad.

backtrackingstringrecursionhash-table

02

Intuition

💡

Your first instinct is to write nested loops: one loop per digit, each walking that digit's letters. Try it and you stall immediately, because you do not know how many loops to write. Two digits needs two loops, four digits needs four, and the digit count only exists at runtime — you cannot express a variable number of nested for loops in fixed source code. That is the entire reason this is a recursion problem: each recursive call IS one level of the loop nest, and the call stack grows to whatever depth the input demands. So you write a single function that handles one digit — loop over its letters, append one, recurse for the rest, then pop it back off. The invariant is that at index i, the path holds exactly i characters, one contributed by each digit already passed; when i reaches the end of the string the path is a finished combination by construction, no length check needed.

03

Approach

1

Map each digit to its letters

Build a fixed lookup from the character '2' through '9' to the letter block printed on that key. This is not data worth deriving — it is a constant of the physical keypad, so hardcode it as a dictionary and stop thinking about it. Note that 1 and 0 carry no letters and the constraints exclude them, which is why the map starts at 2.

2

Recurse one digit per level

Write a helper taking an index into the digit string and the partially built word. If the index equals the length of the digits, the word is complete — append it to the results and return. Otherwise look up the letters for the current digit, and for each one, append it, recurse with index+1, then remove it. That append-recurse-remove triple is the loop body that the nested-loop version could never write, because the recursion supplies as many levels as there are digits.

3

Guard the empty input

An empty digit string must return an empty list, not a list containing an empty string. If you skip this guard, the base case fires immediately at index 0 and records the empty path, giving you [''] — a wrong answer that passes every other test. Check it once at the top and return early, before the recursion ever starts.

04

Solution & live demo

python

▶1class Solution:
▶2    def letterCombinations(self, digits: str) -> list[str]:
▶3        if not digits:
▶4            return []
▶5 
▶6        pad = {
▶7            '2': 'abc', '3': 'def', '4': 'ghi',
▶8            '5': 'jkl', '6': 'mno', '7': 'pqrs',
▶9            '8': 'tuv', '9': 'wxyz',
▶10        }
▶11 
▶12        res, path = [], []
▶13 
▶14        def backtrack(i: int) -> None:
▶15            if i == len(digits):
▶16                res.append(''.join(path))
▶17                return
▶18            for ch in pad[digits[i]]:
▶19                path.append(ch)
▶20                backtrack(i + 1)
▶21                path.pop()
▶22 
▶23        backtrack(0)
▶24        return res

05

Edge cases

Empty digits string

Return an empty list immediately. Falling into the recursion would record the empty path and wrongly return [''] .

A single digit

The recursion bottoms out after one level and returns that key's letters individually, e.g. '2' gives ['a','b','c'].

Digits 7 or 9, which carry four letters

Nothing special — the loop runs over whatever the map holds, so a four-letter key just widens the branching factor at that level.

Repeated digits such as '22'

Each position is independent, so both levels iterate the same letter block and 'aa', 'ab', ... are all legitimately distinct combinations.

06

Complexity

Time

O(4^n * n)

Space

O(n)

n is the number of digits; 4^n bounds the combination count since no key has more than four letters, and the trailing n is the cost of joining each finished path into a string.