How do you approach Letter Combinations of a Phone Number?

Use a mapping from digit to its corresponding letters.

What is the time complexity of Letter Combinations of a Phone Number?

Time complexity: O(4^n * n) where n is the number of digits. Space complexity: O(n) for the recursion stack.

What are common mistakes on Letter Combinations of a Phone Number?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Letter Combinations of a Phone Number

MediumAlgorithms

Description

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

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

Example 1

Input: digits = "23"

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

Example 2

Input: digits = ""

Output: []

Example 3

Input: digits = "2"

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

Constraints

- 0 <= digits.length <= 4 - digits[i] is a digit in the range ['2', '9'].

Letter Combinations of a Phone Number: approach, complexity and pitfalls

A medium backtracking problem, graded against 6 test cases (3 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 3-step hint ladder

Use a mapping from digit to its corresponding letters.
Think about building combinations one digit at a time using backtracking.
The total number of combinations is the product of the number of letters for each digit.

The optimal approach

Show the approach: Backtracking

Use a recursive backtracking approach. For each digit, try each possible letter and recurse on the remaining digits. Build up the combination string character by character.

Time: O(4^n * n) where n is the number of digits
Space: O(n) for the recursion stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.