Decode Ways
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
A message of digits is decoded with A=1, B=2, ..., Z=26. Count how many ways a digit string can be decoded.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Why is "06" not decodable while "10" is?
- Hint 2Let ways[k] be the ways for the first k digits. Which earlier entries feed it?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Reading a text message that has lost its spaces: "226". Reading the first characters, the next letter might be the single digit (2 = B) or a pair of digits (22 = V). After each position you note the number of ways to read everything so far. A single digit is allowed unless it is 0; a pair is allowed only for 10 to 26. A lone 0 cannot be read at all.
- The obvious way
Recursion trying one or two digits at every position repeats work: O(2^n).
- The key insight
ways[0] = 1 (the empty message). For each length k from 1 to n: if digit k is not '0', add ways[k - 1]; if the two digits ending at k form a number from 10 to 26, add ways[k - 2]. The answer is ways[n].
- The algorithm
- ways[0] = 1.
- Single digit non-zero: add ways[k - 1].
- Two digits in 10..26: add ways[k - 2].
- Return ways[n].
Watch it run
Examples = "226"
Start: one way to read nothing.
ways: 1
Where people slip
- "06" as a pair is not valid: the pair must be at least 10.
- A '0' can only be used as the second digit of 10 or 20.
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 num_decodings(s):
ways = [0] * (len(s) + 1) # ways to read the first k digits
ways[0] = 1 # the empty message
for length in range(1, len(s) + 1):
if s[length - 1] != "0":
ways[length] += ways[length - 1] # the last digit alone is a letter
if length >= 2 and 10 <= int(s[length - 2:length]) <= 26:
ways[length] += ways[length - 2] # the last two digits are a letter
return ways[len(s)]Now 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.