Phone Keypad Words
Problem
An old phone keypad maps each digit to a small group of letters: 2 to abc, 3 to def, 4 to ghi, 5 to jkl. Given a string of those digits, return every letter string it could have been typed as. Order the results by taking each digit's letters left to right. An empty digit string produces no words at all.
Examples
Input: digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Why: three letters on 2 times three letters on 3Input: digits = "4"
Output: ["g", "h", "i"]
Why: a single digit contributes one letter per wordInput: digits = ""
Output: []
Why: edge case, no digits means no word, not one empty wordHints
0 / 3
Each digit is a level of decisions and each of its letters is one branch. Picture the shape of that tree before writing anything.
Carry a list of the letters chosen so far. It is the same list for the whole search, which means it has to be restored between branches.
Recurse on the digit index. Append a letter, recurse into the next digit, then pop the letter back off before trying the next one. When the index passes the last digit, join the list and record it.
Solution
This is the plain choose-explore-un-choose loop with the digit index as the depth. One shared path list holds the letters picked so far; appending is the choice, the recursive call explores it, and popping restores the path for the next branch. The base case fires when the index reaches the end of the digit string, which is the only point a candidate is complete. With k letters per digit and n digits the tree has k to the n leaves, so time is O(n times k to the n) and the recursion depth is O(n).
PADS = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl"}
def keypad_words(digits):
out = []
def build(i, path):
if i == len(digits): # every digit has contributed a letter
out.append("".join(path))
return
for ch in PADS[digits[i]]:
path.append(ch) # choose
build(i + 1, path) # explore
path.pop() # un-choose
if digits:
build(0, [])
return out
words = keypad_words("23")
print(len(words), words[0], words[-1]) # -> 9 ad cf
print(keypad_words("")) # -> []Stuck on the idea rather than the code? The Decision Tree covers it.