Count the ways a string of digits can decode into letters. Each digit can stand alone or pair with the one before it, like climbing stairs.
▼The problem
LeetCode 91 (Medium). Letters are encoded as numbers, A = 1, B = 2, ... Z = 26. Given a string of digits, return the number of ways to decode it (a group with a leading zero, like "06", is not a letter).
Examples (LeetCode's): "12" → 2 (AB, L), "226" → 3 (BZ, VF, BBF), "06" → 0.
The solution
def numDecodings(s):
two, one = 0, 1 # counts two back, one back
for i in range(len(s)):
cur = one if s[i] != '0' else 0
if i > 0 and '10' <= s[i-1:i+1] <= '26':
cur += two
two, one = one, cur
return oneTranscript
Decode Ways. A secret message is sent as digits: A is one, B is two, and so on, up to Z at twenty-six. Count the ways to read the digits back as letters.
One two decodes two ways: A B, or L. Two two six has three: B Z, V F, or B B F. And zero six has none: no letter is zero, and zero six isn't a letter.
The naive way tries both cuts at every step: read one digit or two, then decode the rest. But the same tails get decoded again and again, so the calls grow exponentially.
Better: count from the left. Each new digit can finish the message in two ways. If it isn't zero, it's a letter alone: add the count before it. If the last two digits make ten to twenty-six, they're one letter: add the count from two back. It's climbing stairs, with rules.
In code, keep just two counts, starting with one way to read nothing. For each digit, take the last count if the digit isn't zero, add the one before if the pair is ten to twenty-six, then shift.
Try one one one zero six. One: one way. One one: two. One one one: three. Zero can't stand alone, but one zero is J, so two. And zero six isn't a letter, so six keeps two: A A J F, and K J F.
Each digit is checked once: order n time. And only two counts are kept: order one space.
One digit or two, add up the counts, and mind the zeros. That's Decode Ways.