Skip to content

Volume ITechnology

4.18.8 — Letter Combinations of a Phone Number ​

LeetCode 17 · Medium · ★ Blind 75

The problem ​

On an old phone keypad, each digit maps to some letters. Given a string of digits from 2 to 9, return every letter combination it could spell.

"23"  →  ["ad","ae","af","bd","be","bf","cd","ce","cf"]
""    →  []

At most 4 digits.

The pattern ​

The simplest branching in the chapter. The digits are positions, and each digit's letters are the choices at that position.

Think of this like ordering a combo meal where you must choose one Main, one Side, and one Drink. Your choices for Main are Burger/Pizza, for Side are Fries/Salad. You just blindly pick one from the first category, then one from the second, and combine them. There are no rules saying "if you pick Burger, you can't pick Fries." You just multiply the choices out.

        ""
    /    |    \          digit '2' → a, b, c
   a     b     c
  /|\   /|\   /|\        digit '3' → d, e, f
 ad ae af ...

No constraints, no pruning, no duplicates. Every leaf is an answer. That makes it the cleanest illustration of the four parts from 4.18.0 with the third part empty.

The size of the answer is the product of the digit letter counts — mostly 3 each, with 7 and 9 giving 4.

The solution ​

python
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:  # (1)
            return []                     # the empty input is NOT [""]

        keypad = {  # (2)
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
        }

        result = []  # (3)
        path = []

        def backtrack(i: int):  # (4)
            if i == len(digits):  # (5)
                result.append(''.join(path))
                return

            for letter in keypad[digits[i]]:  # (6)
                path.append(letter)  # (7)
                backtrack(i + 1)  # (8)
                path.pop()  # (9)

        backtrack(0)
        return result
ts
function letterCombinations(digits: string): string[] {
  if (!digits) return [];  // (1)

  const keypad: Record<string, string> = {  // (2)
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
  };

  const result: string[] = [];  // (3)
  const path: string[] = [];

  function backtrack(i: number): void {  // (4)
    if (i === digits.length) {  // (5)
      result.push(path.join(''));
      return;
    }
    for (const letter of keypad[digits[i]]) {  // (6)
      path.push(letter);  // (7)
      backtrack(i + 1);  // (8)
      path.pop();  // (9)
    }
  }

  backtrack(0);
  return result;
}

Line by line ​

(1) No digits means no combinations. Return an empty list straight away. The note below explains why this line is needed.

(2) The letters printed on each phone key.

(3) result collects the finished strings, and path holds the letters chosen so far.

(4) backtrack(i) chooses a letter for digit i.

(5) Every digit has a letter, so path spells one complete combination. ''.join(path) glues the letters into one string.

(6) Try each letter on this digit's key. There is no rule to check: every letter is allowed.

(7) Choose the letter,

(8) choose letters for the remaining digits, and

(9) undo, ready for the key's next letter.

The empty-input guard is the only trap. Without it, backtrack(0) hits the base case immediately and returns [""] — a list containing one empty string, not an empty list. LeetCode wants [], and this is the test case that fails.

Building a list and joining at the end beats string concatenation. In Python, path + letter on strings allocates a new string at every node; a list plus one join at the leaf does not. It also makes the pop() undo natural.

No constraint check anywhere. Every combination is valid, so the loop has no if. That is what makes this the reference version of the template.

Edge cases ​

  • Empty input. Returns [], thanks to line (1).
  • One digit, like "2". The answer is that key's letters: ["a", "b", "c"].
  • Keys with four letters, 7 and 9. The loop in line (6) simply runs four times.

The iterative version ​

python
def letterCombinations(self, digits):
    if not digits: return []
    keypad = {...}
    result = ['']
    for d in digits:
        result = [prefix + letter for prefix in result for letter in keypad[d]]
    return result

Start with one empty string, and for each digit replace the whole list with every existing prefix extended by every letter. The list grows by a factor of 3 or 4 per digit.

This is the same doubling structure as the iterative subsets in 4.18.1, and it is arguably the nicer solution here. Write the recursive one in an interview — the question is testing the template — then mention this.

Complexity ​

O(4^n \times n) where n is the number of digits: at most 4 letters per digit, and O(n) to build each result string.

O(n) space for the recursion, not counting the output.

Since the answer itself has up to 4^n entries, this is optimal.

Trace Table ​

Let's trace digits = "23". The keypad maps 2 to "abc" and 3 to "def".

  1. backtrack(0): i=0, digit is '2', choices are ['a','b','c'].
    • Pick 'a'. Path is ['a']. Call backtrack(1).
      • i=1, digit '3', choices ['d','e','f'].
        • Pick 'd'. Path ['a','d']. Call backtrack(2) -> Base case! Record "ad". Undo 'd'.
        • Pick 'e'. Path ['a','e']. Call backtrack(2) -> Record "ae". Undo 'e'.
        • Pick 'f'. Path ['a','f']. Call backtrack(2) -> Record "af". Undo 'f'.
    • Undo 'a'. Path is [].
    • Pick 'b', repeat process for "bd", "be", "bf".
    • Pick 'c', repeat process for "cd", "ce", "cf".

Where this goes next ​

  • Generate Parentheses — the same shape with a real constraint, which is what turns it from enumeration into pruned search. 4.8.4.
  • Combinations of a dictionary, cartesian products, test matrix generation — all this loop.
  • Autocomplete on a keypad (T9) — the real use. A phone does not generate all combinations and check each one; it walks a trie of the dictionary in step with the digits, so invalid prefixes die immediately. That is 4.15.3's idea applied here, and it is a good thing to volunteer.

What the interviewer will push on ​

"What does the empty input return?" [], not [""]. They are checking whether you noticed.

"What is the complexity?" O(4^n \times n), and note that the output size makes it optimal.

"Can you do it iteratively?" The product-building loop.

"How would a real phone do this?" Walk a trie of the dictionary alongside the digits and prune non-words immediately, rather than generating 4^n strings and filtering.

One thing to volunteer: point out that this problem has no constraint step, which is exactly why it is the clearest example of the backtracking template. Then say what changes when a constraint exists — the branch dies before the recursive call.

Next: 4.18.9 N-Queens — the problem backtracking was invented for, where the pruning changes the runtime by four orders of magnitude.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet