parikshan

letter-combinations-phone

Difficulty: Medium  ·  Topic: Backtracking  ·  Practice it on parikshan: /practice/letter-combinations-phone/start

The story

You build a fraud-detection feature at Truecaller. A user reports a spam number partly from memory: they remember the digits but typed them on an old T9 keypad, where each key maps to multiple letters. They want to search their inbox for any text where the unknown caller signed off with a name whose phone-keypad encoding matches the digits they remember. To do that, the search backend needs every letter combination the digit string could spell, then runs each against the message index.

That is letter-combinations-phone. The pattern recurs in every input-method engine, Swiftkey, Gboard, even old BlackBerry SureType, and in any system that needs to enumerate a Cartesian product of small independent choice sets. License-plate completion in surveillance systems, brand-name guessing in trademark searches, and Mancala-style game-tree warm-ups all share this shape.

This is the simplest backtracking problem you will write, and that is exactly why we lead with it: the choice set is tiny, the base case is obvious, and the recursion has no prune. It is the cleanest place to internalise the apply / recurse / undo skeleton before adding constraints in subsets, permutations, and combination-sum.

What's actually being asked

Given a string of digits from 2 to 9, output every letter combination that the digits could spell on a classic phone keypad. The keypad mapping is fixed; 7 and 9 map to four letters, the rest to three. Print results in alphabetical order.

The naive approach

Three nested loops if you know the input length is exactly three. Four nested loops for length four. Hardcoding loop nesting per length is obviously not a solution; the right tool is a recursion that nests as deep as the input requires. That recursion is the canonical backtracking shape, no prune needed.

The iterative equivalent, build the result by repeated Cartesian-product expansion, is also valid and is arguably more Pythonic. We will see both.

The canonical backtracking skeleton

def backtrack(state):
    if is_solution(state):
        record(state)
        return
    for choice in choices(state):
        apply(state, choice)
        backtrack(state)
        undo(state, choice)

For letter-combinations-phone:

  • state: (path, depth) where depth is the index of the digit being placed.
  • is_solution: depth == len(digits).
  • choices: every letter in PHONE[digits[depth]], iterated in alphabetical order.
  • apply: path.append(letter).
  • undo: path.pop().
  • prune: none. Every combination is valid by construction.

This is the cleanest possible instantiation. No used set, no start index, no prune. The choice set is small (3 or 4) and fixed per depth. Once you have the skeleton in your fingers from this problem, every other backtracking problem is a variation.

The key insight

If you write the keypad map with letters in alphabetical order, and always iterate the map in order, the deepest letter changes fastest and the leftmost letter changes slowest. The finished combinations come out in alphabetical order automatically. No sort step. This is the same guarantee itertools.product gives you on alphabetical sequences.

This is a small detail worth internalising: lex order in backtracking is a consequence of iterating choices in lex order, not of a final sort. The same property held in subsets and permutations once we sorted the input. Here it holds because the keypad map is written alphabetically. Sort once, never again.

Step-by-step approach

  1. Define PHONE = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}.
  2. Hold an output list and a path.
  3. Define dfs(i). Base: if i == len(digits), append ''.join(path) and return.
  4. For each letter c in PHONE[digits[i]]: push c, recurse dfs(i + 1), pop.
  5. Call dfs(0). Print the count, then every combination on its own line.

Worked example

digits = "23"

PHONE['2'] = "abc", PHONE['3'] = "def". DFS unfolds:

  • depth=0, push 'a'.
    • depth=1, push 'd'. record "ad". pop.
    • push 'e'. record "ae". pop.
    • push 'f'. record "af". pop.
  • pop. push 'b'.
    • record "bd", "be", "bf".
  • pop. push 'c'.
    • record "cd", "ce", "cf".

Nine combinations, alphabetical order. Matches the spec exactly.

The iterative one-liner

result = ['']
for d in digits:
    result = [r + c for r in result for c in PHONE[d]]

After every digit, result holds every partial combination of digits seen so far, in alphabetical order. The list-comprehension version is shorter, faster (no function-call overhead), and produces identical output. Use this in production Python; use the recursion when interview pressure asks for the explicit pattern.

A C++ or Java implementation would write the recursion because the iterative version's allocation pattern is less clean in those languages. In Python, the iterative version wins.

Complexity

Let L = len(digits). Each digit maps to 3 or 4 letters, so the total combinations are between 3^L and 4^L. Each combination is L characters.

  • Time: O(L * 4^L) in the worst case (all 7s and 9s).
  • Space: O(L) for the recursion stack; O(L * 4^L) for the output.

At L = 7 (the constraint ceiling) and all 9s, that is 7 * 16384 = ~115K characters, well within the output budget.

Common pitfalls

  • Empty input handling: the problem guarantees |digits| >= 1, so you do not need an empty-input branch, but interview variants often allow it. If empty, return [] (no combinations), not [""].
  • Joining vs. appending: the output is one string per combination, not a list of characters. ''.join(path) is the right idiom; str(path) will emit a Python list literal.
  • Mutable defaults: do not write def dfs(i, path=[]). Python's default-argument trap means the same list persists across calls. Pass path explicitly or hold it in an enclosing scope.
  • Sorting at the end: unnecessary if the map is alphabetical. Generated code sometimes sorts "to be safe", wasteful, but not wrong.

Where this shows up in the enterprise

  • Gboard / Swiftkey: T9-style autocomplete on legacy keypads, still shipped on feature phones across rural markets.
  • Truecaller / Hiya: spam-name lookup when the user remembers a number partly by name.
  • Apple Spotlight / Alfred: typed-substring expansion across small fixed-choice alphabets.
  • Amazon Echo / Google Home: voice-to-text fallback when a partial digit sequence is heard.
  • License-plate readers: ALPR systems running fuzzy matches against partially-obscured plates.
  • Trademark search engines: enumerate every legible variant of a brand spelling.
  • Crossword solvers: enumerate every word matching a fixed letter pattern with wildcards.

The deeper lesson is that Cartesian product of small independent choice sets is everywhere. Once you see the shape, you stop reaching for nested loops and start reaching for itertools.product or a four-line DFS.

Variants you'll see elsewhere

  • generate-parentheses: same DFS shape, but with a prune (open count <= n, close count <= open).
  • restore-ip-addresses: pick where to split a digit string into four valid octets, Cartesian product with bound constraints.
  • palindrome-partitioning: split a string into palindromic prefixes, same skeleton, different validity check.
  • word-search: pick adjacent grid cells matching letters of a target word, DFS with backtracking on a grid.

letter-combinations-phone is the warm-up. Once it is fluent, the others are minor variations.

How parikshan turns this into a learning loop

This problem is the canonical entry point to backtracking on the platform: hint 4 spells out the entire DFS, but you should never need it. Practice mode lets you iterate freely with AI assistance, ask the assistant to Explain the apply/undo loop, Find Bugs in your base case, or Optimise your recursion to the iterative form. Exam mode flips the cost: every AI request docks integrity, so you write the skeleton from memory. If you can write letter-combinations-phone from a blank file in under two minutes in exam mode, the apply / recurse / undo pattern is yours and you are ready for subsets, permutations, and combination-sum.

In the AI-integrated workspace

Three things to verify in agent-generated code:

  1. The keypad map is alphabetical in each value, so the iteration order produces sorted output without a post-sort.
  2. The recursion records ''.join(path), not the list itself, and not a stale shared reference.
  3. The iterative variant is preferable in Python; if the agent writes the recursion, ask whether the iterative form is acceptable. In production code it is almost always faster.

letter-combinations-phone is the simplest backtracking problem you can name out loud. The skill is to spot, in 50 lines of agent-generated code, that it is exactly this problem under a different name, and to swap in five lines of itertools.product instead. That recognition is what separates senior engineers who direct agents from juniors who review agent diffs line by line.