At each position in the string, there are at most two moves: decode the current digit as one letter (valid when it is between 1 and 9), or decode the current digit together with the next one as a single letter (valid when the pair forms a number between 10 and 26). The total number of decodings is the number of distinct ways to make these choices across the entire string.

Zeros are the complication. A '0' cannot stand alone; it can only close a two-digit group, and only "10" and "20" are valid. A '0' preceded by anything other than '1' or '2' (including another '0') cannot be decoded at all, which makes the answer for the whole string 0.

The structure fits dynamic programming: the number of ways to decode a prefix depends only on the counts for the one-shorter and two-shorter prefixes, depending on whether the last move consumed one digit or two.

Key Constraints:

Intuition

Make decisions from left to right. At position i, try taking one digit, and also try taking two digits when the pair is between 10 and 26. Each valid option recurses on the rest of the string, and the counts from both options add up.

Reaching the end of the string is the base case and counts as one valid decoding: every digit has been consumed. A '0' at the current position returns 0, since zero maps to no letter on its own.

Algorithm

Example Walkthrough

Input:

Working back from the end: decode(3) is the base case and returns 1. decode(2) sees '6'; only the single digit applies (nothing follows it), so it returns decode(3) = 1. decode(1) sees '2'; taking it alone gives decode(2) = 1, and taking "26" gives decode(3) = 1, so it returns 2. decode(0) sees '2'; taking it alone gives decode(1) = 2, and taking "22" gives decode(2) = 1, for a total of 3. The three decodings are (2 2 6), (2 26), and (22 6).

Code

There are only n distinct call arguments, so the exponential cost comes entirely from recomputing the same suffixes. Caching each decode(i) the first time it is computed removes the repetition.

Intuition

The brute force recursion solves the same subproblem repeatedly. In the recursion tree for "1234", decode(2) is reached twice: once after taking '1' and '2' as single digits, and once after taking "12" as a pair. For longer strings the duplication compounds at every level.

The result of decode(i) depends only on i, not on how the recursion arrived there, so it can be cached. Before computing decode(i), check the cache and return the stored result on a hit; otherwise compute it, store it, and return it. Each index is then computed at most once, which brings the exponential recursion down to linear time.

Algorithm

Example Walkthrough

For s = "226", the memo array records the result for each starting index:

Code

Memoization removes the redundant work but keeps the recursion and its call stack. The same table can be filled iteratively, left to right, with a plain loop.

Intuition

Define dp[i] as the number of ways to decode the first i characters. Every decoding of that prefix ends in one of two ways, so:

The base case is dp[0] = 1: the empty prefix has exactly one decoding, the empty one. This is the same recurrence as Climbing Stairs, with a validity check attached to each term. When the string has no zeros and every adjacent pair is at most 26, both terms always apply, the recurrence becomes exactly dp[i] = dp[i-1] + dp[i-2], and the answer is a Fibonacci number. A string of thirty '1's has 1,346,269 decodings, which is Fib(31). The zeros and the 10-26 bound are what separate this problem from plain Fibonacci: they can drop either term, or both, at any position.

Algorithm

Example Walkthrough

For s = "226", the table fills left to right:

Code

The loop reads only dp[i-1] and dp[i-2], so the full array is unnecessary.

Intuition

Two variables replace the array: prev1 holds dp[i-1] and prev2 holds dp[i-2]. After computing the count for position i, both shift forward one step. This is the same rolling-variable optimization that computes Fibonacci numbers in constant space. When the loop ends, prev1 holds dp[n], the answer.

One detail moves to the front: the code initializes prev1 to 1 unconditionally, so a string starting with '0' must be handled by an early return 0 instead of by setting prev1 = 0.

Algorithm

Example Walkthrough

For s = "11106", which contains both a forced pair ("10") and an invalid pair ("06"):

Code