MediumHash TableStringBacktrackingUpdated Sep 2026

17. Letter Combinations of a Phone Number

Asked at Google, Microsoft, Oracle, Apple and 1 more

Difficulty

Medium

Time

O(4^n * n)

Space

O(n)

Pattern

Hash Table

Companies

5

Problem

You are given a string digits that contains only the characters '2' through '9'. Each digit stands for a group of letters, just like the buttons on an old phone keypad: 2 is abc, 3 is def, 4 is ghi, 5 is jkl, 6 is mno, 7 is pqrs, 8 is tuv, and 9 is wxyz.

Return every string you can build by picking one letter from each digit, in order. If digits has length n, each answer string also has length n: the first character comes from the first digit, the second from the second digit, and so on. The order of the strings in your answer does not matter.

For example, with digits = "23" you pick one letter from abc and one from def, giving ad, ae, af, bd, be, bf, cd, ce, cf. The digits 0 and 1 never appear in the input, so you do not need to handle them.

One letter per digit

digit 2 -> a b cdigit 3 -> d e fpick one from eachThe keypad mapping turns each digit into a small set of letters.answersadaeafbdbebfcdcecfAll 9 strings, grouped by the first letter: a..., b..., c...
Each answer takes one letter from the first digit and one from the second, so "23" gives 3 × 3 = 9 strings.

Constraints

  • ●1 <= digits.length <= 4
  • ●digits[i] is a digit in the range ['2', '9']

Examples

Example 1
Inputdigits = "23"
Output["ad","ae","af","bd","be","bf","cd","ce","cf"]
WhyDigit 2 gives three choices (a, b, c) and digit 3 gives three choices (d, e, f). Pairing every choice from the first digit with every choice from the second gives 3 × 3 = 9 strings.
Example 2
Inputdigits = "2"
Output["a","b","c"]
WhyThere is only one digit, so each answer is just one of its three letters.

Asked At

5 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MicrosoftMediumView all Microsoft questions →
OracleMediumView all Oracle questions →
AppleMediumView all Apple questions →
LinkedInMediumView all LinkedIn questions →

How to Think About It

1

Key insight: each digit maps to 3-4 letters. For digits "23", digit 2 maps to "abc" and digit 3 maps to "def". The result is all combinations: ad, ae, af, bd, be, bf, cd, ce, cf. Use backtracking to build combinations one digit at a time.

2

Data structure: create a hash map mapping each digit to its letters: 2="abc", 3="def", 4="ghi", 5="jkl", 6="mno", 7="pqrs", 8="tuv", 9="wxyz". Digits 0 and 1 map to nothing.

3

The backtracking pattern: maintain a current combination string. For the current digit, try each of its mapped letters. Add the letter to the combination, recurse on the next digit. When the combination length equals the input length, add it to the result. Backtrack by removing the last letter.

4

Edge cases: empty string returns empty list. Single digit returns its mapped letters. Digit with no mapping (0, 1) should be skipped or handled. Very long input strings produce many combinations (4^n worst case for "7777").

Optimal Approach

Step 1: Create a hash map for digit-to-letter mapping.
Step 2: Handle edge case: if input is empty, return empty list.
Step 3: Use backtracking with parameters: current combination, current index in digits.
Step 4: At each step, get the letters for the current digit. For each letter, add it to the combination and recurse on the next digit.
Step 5: When the combination length equals the digits length, add it to the result.

Walkthrough for "23":

  • digits = ["2", "3"], mapping = {2:"abc", 3:"def"}
  • backtrack("", 0):
    • digit "2" -> "abc"
    • backtrack("a", 1):
      • digit "3" -> "def"
      • backtrack("ad", 2): len==2, add "ad"
      • backtrack("ae", 2): add "ae"
      • backtrack("af", 2): add "af"
    • backtrack("b", 1):
      • backtrack("bd", 2): add "bd"
      • backtrack("be", 2): add "be"
      • backtrack("bf", 2): add "bf"
    • backtrack("c", 1):
      • backtrack("cd", 2): add "cd"
      • backtrack("ce", 2): add "ce"
      • backtrack("cf", 2): add "cf"
  • Result: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

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

Backtracking builds one letter at a time

combinationafrontbackStep 1 — pick 'a' for digit 2 and recurse to digit 3.combinationadfrontbackStep 2 — pick 'd' for digit 3. Length equals 2, sosave "ad".combinationbfrontbackStep 3 — backtrack: remove 'd', then remove 'a', andtry 'b' next.if index == len(digits): saveelse: for ch in phone[digits[index]]recurse(index + 1)
Try a letter, go deeper, then undo it and try the next letter.
ComplexityTime O(4^n * n)Space O(n)There are at most 4^n combinations and each one costs n work to build; the recursion stack holds at most n frames.

What Trips People Up in Real Interviews

1

Including digits 0 and 1 in the mapping. Digits 0 and 1 have no letters on a phone keypad. If the input contains them, skip or return an empty list. Do not map them to empty strings and produce empty combinations.

2

Using BFS or iterative queue-based generation instead of backtracking. Both work, but interviewers often want to see the recursive backtracking pattern with explicit add/remove (or string concatenation) for clarity.

3

Forgetting that the result length is O(4^n) where n is the number of digits. For input "7777", that is 4^4 = 256 combinations. If the interviewer asks about scalability, mention this bound.

4

Building combinations with a mutable list and appending/removing characters instead of passing a new string. Both are valid, but mixing them up (e.g., forgetting to remove after recursion) causes incorrect results.

5

Not validating the input. Digits must be 2-9. If the input contains 0, 1, or non-digit characters, handle it gracefully. The problem says digits are from 2-9, but defensive coding matters in interviews.

Solution Code

O(4^n * n) time
def letterCombinations(digits):
    if not digits:
        return []
    phone = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    result = []

    def backtrack(combination, index):
        if index == len(digits):
            result.append(combination)
            return
        for ch in phone[digits[index]]:
            backtrack(combination + ch, index + 1)

    backtrack("", 0)
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Letter Combinations of a Phone Number problem?

Given a string of digits from 2-9, return all possible letter combinations that the number could represent (like old phone keypads). This problem tests your ability to use `backtracking` to generate all combinations from a mapping.

How do you solve Letter Combinations of a Phone Number?

The optimal approach runs in O(4^n * n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Letter Combinations of a Phone Number?

Letter Combinations of a Phone Number is asked at Google, Microsoft, Oracle, Apple, LinkedIn. It is a medium difficulty problem.

What are common mistakes on Letter Combinations of a Phone Number?
  • Including digits 0 and 1 in the mapping. Digits 0 and 1 have no letters on a phone keypad. If the input contains them, skip or return an empty list. Do not map them to empty strings and produce empty combinations.
  • Using BFS or iterative queue-based generation instead of `backtracking`. Both work, but interviewers often want to see the recursive `backtracking` pattern with explicit add/remove (or string concatenation) for clarity.
  • Forgetting that the result length is `O(4^n)` where n is the number of digits. For input "7777", that is 4^4 = 256 combinations. If the interviewer asks about scalability, mention this bound.
  • Building combinations with a mutable list and appending/removing characters instead of passing a new string. Both are valid, but mixing them up (e.g., forgetting to remove after recursion) causes incorrect results.
  • Not validating the input. Digits must be 2-9. If the input contains 0, 1, or non-digit characters, handle it gracefully. The problem says digits are from 2-9, but defensive coding matters in interviews.