Decode Digit Message
Problem
Letters were turned into numbers, A to Z becoming 1 to 26, and the numbers were then written down with no separators. Count how many different letter sequences could have produced a given digit text. A group of digits is only a letter when it reads as 1 through 26, so no group may start with a zero.
Examples
Input: digits = "226"
Output: 3
Why: the cuts 2 26, 22 6 and 2 2 6 are all legalInput: digits = "11106"
Output: 2
Why: the zero must join the digit before it, which rules out most cutsInput: digits = "0"
Output: 0
Why: edge case, nothing decodes a leading zeroHints
0 / 3
Look at the end of the text rather than the start: the final letter took either the last digit alone or the last two digits together.
That gives a count for each prefix in terms of the counts for the one and two shorter prefixes, which means the whole text can be filled in from left to right.
Sweep the digits carrying the counts for the previous two prefixes. Add the one-shorter count when the current digit is not a zero, and add the two-shorter count when the current digit and the one before it read as a number between 10 and 26. Slide the two carried values along and continue.
Solution
The last letter of any decoding consumes either one digit or two, so the number of decodings of a prefix is the sum of the counts for the prefixes one and two digits shorter, each guarded by whether that final group is legal. A zero can never stand alone, and a pair only counts when it lands between 10 and 26, which is what rules out both leading zeros and oversized pairs. Only the last two counts are ever needed, so two variables replace the table. Time is O(n) and space is O(1).
def count_decodings(digits):
if not digits:
return 0
prev, cur = 1, (0 if digits[0] == "0" else 1) # empty prefix, then one digit
for i in range(1, len(digits)):
total = 0
if digits[i] != "0": # this digit stands on its own
total += cur
if 10 <= int(digits[i - 1:i + 1]) <= 26: # the pair reads as one letter
total += prev
prev, cur = cur, total
return cur
print(count_decodings("226")) # -> 3
print(count_decodings("11106")) # -> 2
print(count_decodings("0")) # -> 0Stuck on the idea rather than the code? Top-Down vs Bottom-Up covers it.