Medium Backtrack+Prune Backtracking
In plain English: Given phone number digits, list all possible letter combinations from the keypad (like T9).
Each digit maps to 3-4 letters. Build combinations by choosing one letter per digit and backtracking — the recursion tree has at most 4^n leaves.
Prompt
Given a string of digits 2-9, return all possible letter combinations that the number could represent (phone keypad mapping).
Try to write it from scratch before scrolling down.
Solution
def letter_combinations(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(idx, path):
if idx == len(digits):
result.append(''.join(path))
return
for c in phone[digits[idx]]:
path.append(c)
backtrack(idx + 1, path)
path.pop() # backtrack
backtrack(0, [])
return result
# Test: letter_combinations("23") == ["ad","ae","af","bd","be","bf","cd","ce","cf"]