Letter Combinations of a Phone Number
Asked at Google, Microsoft, Oracle, Apple
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Microsoft | Medium | View all Microsoft questions → |
| Oracle | Medium | View all Oracle questions → |
| Apple | Medium | View all Apple questions → |
How to Think About It
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.
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.
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.
Visual walkthrough for "23":
Digit 2 -> "abc", Digit 3 -> "def"
Start: combination = ""
- Try a: combination = "a". Recurse on digit 3.
- Try d: combination = "ad". Length=2, done. Add "ad". Backtrack.
- Try e: combination = "ae". Length=2, done. Add "ae". Backtrack.
- Try f: combination = "af". Length=2, done. Add "af". Backtrack.
- Try b: combination = "b". Recurse on digit 3.
- Try d: "bd". Add. Try e: "be". Add. Try f: "bf". Add.
- Try c: combination = "c". Recurse on digit 3.
- Try d: "cd". Add. Try e: "ce". Add. Try f: "cf". Add.
Result: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Letter Combinations of a Phone Number?
Letter Combinations of a Phone Number is asked at Google, Microsoft, Oracle, Apple. 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.