Given a string of digits 2-9, return every letter string the number could spell on an old phone keypad. For "23" the answer is ad, ae, af, bd, be, bf, cd, ce, cf.
Build the answer one digit at a time. At position i, try each letter for digits[i], recurse to i + 1, then undo the choice.
PHONE = {"2":"abc","3":"def","4":"ghi","5":"jkl",
"6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
def letter_combinations(digits):
if not digits:
return []
out, path = [], []
def go(i):
if i == len(digits):
out.append("".join(path))
return
for ch in PHONE[digits[i]]:
path.append(ch)
go(i + 1)
path.pop()
go(0)
return out
Start with [""] and, for each digit, extend every partial string with each of its letters. It produces the same order and avoids recursion entirely.
def letter_combinations(digits):
if not digits:
return []
res = [""]
for d in digits:
res = [p + ch for p in res for ch in PHONE[d]]
return res
With n digits, there are at most 4n combinations (digits 7 and 9 have four letters), and each takes O(n) to build, so O(n * 4n) time. Output size dominates; the recursion itself uses O(n) extra space.
[""] for empty input instead of [].Disclosure: I work on Linkjob AI. If you want structured practice for interviews like this, linkjob.ai can help you rehearse and get real-time hints.