Decode Ways

Count ways to decode digits where 1 through 26 map to letters.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Decode Ways: At each digit, add one-back decodings for a valid single digit and two-back decodings for a valid 10..26 pair.

Input and goalCount ways to decode digits where `1` through `26` map to letters.

Initialize after the leading 2For text "2101", the leading digit is nonzero. Set two_back = 1 and one_back = 1: prefix "2" has one decoding.

index 020110213

prefix"2"statetwo_back = 1; one_back = 1

Recognize it

Use it when each encoded token consumes one or two adjacent symbols, validity depends on the local symbol or pair, and the task asks for the number of complete parses.

Keep true

Before index i, one_back counts decodings through i-1 and two_back through i-2; current sums exactly the valid single-digit and two-digit ways ending at i.

Reuse it

For variable-width parsing, sum counts from earlier boundaries only when the token ending at the current boundary is valid; zeros often eliminate the width-one transition.

Pattern: DP with one-digit and two-digit choices.

Simple idea: A nonzero current digit can extend every decoding from one position back. A valid two-digit number from 10 through 26 can extend every decoding from two positions back.

def num_decodings(text: str) -> int:
   if not text or text[0] == "0":
      return 0

   two_back = one_back = 1
   for index in range(1, len(text)):
      current = one_back if text[index] != "0" else 0
      if 10 <= int(text[index - 1 : index + 1]) <= 26:
         current += two_back
      two_back, one_back = one_back, current
   return one_back

Cost: $O(n)$ time and $O(1)$ space.