Decode ways
Each position can be reached by reading one digit or two, but not every reading is valid — check before counting. About 12 minutes.
Read one digit or two
Read the digits from left to right. At each point, the last piece you read was either one digit or two digits.
One digit works as long as it isn't 0, because no letter is 0. Two digits work when they make a number from 10 to 26. So the readings of everything so far are the readings that end with a single digit, plus the readings that end with a pair. Each of those is an answer you've already worked out, one or two digits back.
Before reading any digits there's exactly one way to decode nothing: do nothing. That 1 is the seed.
Start with the empty message
Before reading anything there's exactly one way to decode nothing: do nothing. That 1 is the seed everything grows from.
For "226": after the first 2 there's 1 reading. After the second 2 there are 2 (read it alone, or read 22). The 6 can be read alone (2 readings carry over) or as 26 (1 reading from before the pair): 3 in total. And a string that starts with 0 can't be read at all.
ways = [1] + [0] * len(s)
for i in range(1, len(s) + 1):
if s[i - 1] != "0":
ways[i] += ways[i - 1]
if i >= 2 and "10" <= s[i-2:i] <= "26":
ways[i] += ways[i - 2]
return ways[len(s)]s = "06". How many ways can it be decoded?
- A0
- B1
Show the answer
0. The first digit is '0', which is never valid alone, and "06" as two digits is 6, not between 10 and 26.
Decode ways
s is a string of digits, standing for a message where 'A' to 'Z' were mapped to the numbers 1 to 26 and written with no separators. Return the number of different ways s could have been decoded back into letters.
s = "226" → 3
1 ≤ s.length ≤ 1,000 · every character of s is a digit '0'-'9'