Letter Combinations of a Phone Number
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
On an old phone keypad each digit 2-9 maps to letters (2: abc, 3: def, ...). Return all letter combinations a digit string could mean.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What are the words after only the first digit?
- Hint 2For the next digit, extend every word with every letter on that key.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Typing a text on an old Nokia where 2 could mean a, b or c. For "23" you first have three words: a, b, c. Then the digit 3 offers d, e, f: every existing word is extended with each of the three letters, giving 3 x 3 = 9 words. Each digit multiplies the number of words by the size of its menu.
- The obvious way
The answer itself has up to 4^n words, so this is optimal.
- The key insight
Start with a list holding one empty word. For each digit, build a new list: for every word so far and every letter of the digit, word + letter. Return the list after the last digit (empty digits give an empty answer).
- The algorithm
- Empty digits: return [].
- words = [""].
- For each digit, replace words with every word + each letter on the key.
- Return words.
Watch it run
Exampledigits = "23"
Start with one empty word.
[""]
Where people slip
- Return an empty list for empty input, not [""].
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def letter_combinations(digits):
if not digits:
return []
keypad = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
words = [""] # one empty word to start
for digit in digits:
words = [word + letter for word in words for letter in keypad[digit]]
return wordsNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.