What is the brute force approach and complexity for Letter Combinations of a Phone Number?

Start from [""]; for each digit, extend every partial word by its letters with time complexity O(n · 4ⁿ) and space complexity O(n · 4ⁿ).

What is the optimal approach and complexity for Letter Combinations of a Phone Number?

Recurse on the digit position; push a letter, recurse, then pop it with optimal time complexity O(n · 4ⁿ) and space complexity O(n).

How do you identify the pattern for Letter Combinations of a Phone Number?

Look for key signals in the prompt: "each digit maps to letters" indicates Every position has its own set of choices. Position i uses digit i's letters only.; "every combination of letters" indicates Visit every full word: one letter per position, so the recursion goes by position index.; "return all possible words" indicates The answer is a list of strings. Copy each word when it is complete..

Letter Combinations of a Phone Number

Medium·LeetCode #17 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given a string of digits from 2 to 9. Each digit is a button on an old phone keypad, and each button stands for some letters:

2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz

Make words by picking one letter for each digit, in order. Return every word you can make.

You may return the words in any order.

Input

A string digits of characters 2 to 9. The problem guarantees at least one digit. If the string is empty, return [], not a list holding one empty word.

Output

A list of every word. Each word has one letter per digit.

Example 1

Input: digits = "23"

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Digit 2 gives a, b or c. Digit 3 gives d, e or f. Every pair (one letter from each) makes a word, so there are 3 × 3 = 9 words.

Example 2

Input: digits = "2"

Output: ["a","b","c"]

Digit 2 has three letters, so there are three one-letter words.

Constraints

• 1 ≤ digits.length ≤ 4
• digits[i] is a digit from 2 to 9

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“each digit maps to letters”

→ Every position has its own set of choices. Position i uses digit i's letters only.

“every combination of letters”

→ Visit every full word: one letter per position, so the recursion goes by position index.

“return all possible words”

→ The answer is a list of strings. Copy each word when it is complete.

Approach Complexity Ladder

Brute Force — build all partial words level by levelO(n · 4ⁿ)O(n · 4ⁿ)

Start from [""]; for each digit, extend every partial word by its letters

Optimal — recursion by digit position with one shared wordO(n · 4ⁿ)O(n)

Recurse on the digit position; push a letter, recurse, then pop it

Brute Force Intuition

Keep a list of partial words, starting with one empty word. For each digit, make a new list: take every partial word and add each letter of that digit to it. After the last digit, the list holds every full word.

Recognition rule for this sub-pattern:

Choose K items in increasing index order so the same group is never generated twice.

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture