Decode Ways: DP with gated transitions

By the time you reach LeetCode 91, you've already seen the skeleton. Climbing Stairs is ways(i) = ways(i+1) + ways(i+2), no conditions attached — any step can reach the next. Decode Ways uses the exact same skeleton, but wraps both transitions in guards. The digit at position i has to earn the right to use each path. That conditional gating is the only thing this problem teaches. Get it clearly, and the rest writes itself.

The problem

Given a string of digits, count the number of distinct ways to decode it using the mapping "1" -> 'A', "2" -> 'B', ..., "26" -> 'Z'. A '0' cannot be decoded on its own, and leading zeros make a two-digit group invalid. Full statement: LeetCode 91.

Constraints:
- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s).

The constraints are tight: 1 <= s.length <= 100, and s contains only digits. The answer fits in a 32-bit integer, so no overflow concern. The small bound on length means even O(n) with a full array is fine — the real question is correctness, not performance. But the bound also tells you something else: with only 100 characters, a naive recursive exploration without memoization would still be fast in the worst case (because the recursion tree branches at most 2 ways per node and depths out at 100). The point of memoization here is correctness of reasoning, not survival under a constraint.

Two edge cases do all the damage. A '0' at position i cannot be decoded as a single character (there's no letter 0). And a two-digit slice s[i..i+1] is only valid if it lands between 10 and 26 — "30" and "00" are dead ends, "26" is valid, "27" is not.

Strip those two guards away and you literally have Climbing Stairs. The recurrence is dp[i] = dp[i+1] + dp[i+2]. The guards are the problem.

Recognizing the pattern

The keywords that flag this as gated linear DP: "number of ways," "decode," "partition string into valid segments." Whenever you're splitting a sequence into pieces and each split point has a validity condition, you're likely looking at this same shape.

The constraint that only 1-2 digit groupings are valid (mapping to 1-26) is what keeps the lookahead bounded. If valid groupings could be arbitrary length, you'd need something closer to Word Break. Here, each state only ever looks at i+1 and i+2. That's what makes the two-variable optimization possible later.

The alphabet ceiling at 26 is not incidental — it's what limits two-digit groups to [10, 26] and completely excludes anything starting with '0'. A '0' in the middle of the string is a silent blocker: it kills the single-digit path at its position, and can only be "saved" by a preceding '1' or '2' that forms "10" or "20".

Approach 1: recursion with memoization

The natural first pass defines a recursive function decode(i) = "how many ways can I decode the suffix starting at position i?" At the empty suffix it's 1. At a '0' it's 0. Otherwise, take one digit (always valid if not '0') and optionally two digits (if the pair is in range).

class Solution:
    def numDecodings(self, s: str) -> int:
        memo = {}
        def decode(index):
            if index == len(s):
                return 1
            if index in memo:
                return memo[index]
            if s[index] == '0':
                memo[index] = 0
                return 0
            result = decode(index + 1)
            if index + 1 < len(s):
                two_digit = int(s[index:index+2])
                if 10 <= two_digit <= 26:
                    result += decode(index + 2)
            memo[index] = result
            return result
        return decode(0)

To see the branching structure, here's the recursion tree for s = "226". Nodes that return 0 are dead ends; nodes marked *memo* were computed earlier and are simply returned:

Walk through s = "12" to confirm the code. decode(0): s[0]='1', not zero, so result = decode(1). Then check "12" = 12, which is in range, so result += decode(2). decode(1): s[1]='2', result = decode(2) = 1, no room for two digits. decode(2) is base case, returns 1. So decode(1) = 1, decode(0) = 1 + 1 = 2. The two decodings: "A-B" and "L". Correct.

The memoization is mandatory. Without it, overlapping subproblems explode the same way they do in naive Fibonacci. With it, every index is visited exactly once.

The C# version is structurally identical:

public class Solution {
    private Dictionary<int, int> memo;
    private string s;
    public int NumDecodings(string s) {
        this.s = s;
        this.memo = new Dictionary<int, int>();
        return Decode(0);
    }
    private int Decode(int index) {
        if (index == s.Length) return 1;
        if (memo.ContainsKey(index)) return memo[index];
        if (s[index] == '0') { memo[index] = 0; return 0; }
        int result = Decode(index + 1);
        if (index + 1 < s.Length) {
            int twoDigit = int.Parse(s.Substring(index, 2));
            if (twoDigit >= 10 && twoDigit <= 26)
                result += Decode(index + 2);
        }
        memo[index] = result;
        return result;
    }
}

I use the top-down version for reasoning about correctness. The recursive structure makes the gating explicit — you can see exactly where each guard sits before the recursive call. When debugging, I can trace a single call stack and watch which branches die at '0' and which ones fail the 10..26 check. It's a cleaner mental model.

That said, the recursion overhead is real. For n = 100, the call stack depth is bounded, but the function call overhead exists. The bottom-up version avoids it entirely.

Time: O(n) — each index computed once via memoization. Space: O(n) for both the memo dictionary and the call stack.

Approach 2: bottom-up DP, filling right to left

Flip the direction. dp[i] = number of ways to decode s[i..n-1]. Base case: dp[n] = 1 (empty suffix, one valid decoding). Build from right to left.

The direction matters here in a way it doesn't for Climbing Stairs. In Climbing Stairs, dp[i] naturally accumulates from dp[i-1] and dp[i-2] when going left to right. In Decode Ways, dp[i] looks forward to dp[i+1] and dp[i+2], so the fill order has to be reversed.

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                dp[i] = 0
            else:
                dp[i] = dp[i + 1]
                if i + 1 < n:
                    two_digit = int(s[i:i+2])
                    if 10 <= two_digit <= 26:
                        dp[i] += dp[i + 2]
        return dp[0]

Walk through s = "226" step by step:

dp[3] = 1               // base: empty suffix
dp[2] = dp[3] = 1       // '6' != '0'; no room for two-digit
dp[1] = dp[2] + dp[3]   // '2' != '0'; "26" is in [10,26]
      = 1 + 1 = 2
dp[0] = dp[1] + dp[2]   // '2' != '0'; "22" is in [10,26]
      = 2 + 1 = 3

Three decodings: "2-2-6" (B-B-F), "22-6" (V-F), "2-26" (B-Z). Correct.

Now s = "06":

dp[2] = 1               // base
dp[1] = dp[2] = 1       // '6' != '0'; no room for two-digit
dp[0] = 0               // '0' -> immediately zero

Returns 0. The guard at s[0] == '0' kills the entire string. That's the gate at work — the single-digit path dies immediately, and there's no valid two-digit path starting at 0 because "06" is not in [10, 26].

The C# version using the full array:

public class Solution {
    public int NumDecodings(string s) {
        int n = s.Length;
        int[] dp = new int[n + 1];
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                if (i + 1 < n) {
                    int twoDigit = int.Parse(s.Substring(i, 2));
                    if (twoDigit >= 10 && twoDigit <= 26)
                        dp[i] += dp[i + 2];
                }
            }
        }
        return dp[0];
    }
}

Time: O(n). Space: O(n) for the full dp array. This works, but notice that at each step i, you only ever read dp[i+1] and dp[i+2]. Never anything further back. That means the full array is overkill.

The version I'd actually ship: O(1) space

Two variables replace the array. next1 holds dp[i+1], next2 holds dp[i+2]. After computing current = dp[i], shift both forward before moving to i-1.

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        next1, next2 = 1, 1   # dp[n] = 1; dp[n+1] = 1 (sentinel)
        for i in range(n - 1, -1, -1):
            current = 0
            if s[i] != '0':
                current = next1
                if i + 1 < n:
                    two_digit = int(s[i:i+2])
                    if 10 <= two_digit <= 26:
                        current += next2
            next2, next1 = next1, current
        return next1

The C# version — this is what I'd leave in a code review:

public class Solution {
    public int NumDecodings(string s) {
        int n = s.Length;
        int next1 = 1, next2 = 1;   // dp[i+1], dp[i+2]
        for (int i = n - 1; i >= 0; i--) {
            int current = 0;
            if (s[i] != '0') {
                current = next1;
                if (i + 1 < n) {
                    int twoDigit = (s[i] - '0') * 10 + (s[i + 1] - '0');
                    if (twoDigit >= 10 && twoDigit <= 26)
                        current += next2;
                }
            }
            next2 = next1;
            next1 = current;
        }
        return next1;
    }
}

The (s[i] - '0') * 10 + (s[i + 1] - '0') trick avoids int.Parse and Substring allocation on every iteration. Small thing, but it's the right reflex — when you're in a tight loop, avoid heap allocations.

Trace through s = "226" with variables to confirm:

i=2: s[2]='6', current = next1 = 1; no i+1 -> next2=1, next1=1
i=1: s[1]='2', current = next1 = 1; "26"=26 in [10,26] -> current += next2=1 -> current=2
                                     next2=1, next1=2
i=0: s[0]='2', current = next1 = 2; "22"=22 in [10,26] -> current += next2=1 -> current=3
                                     next2=2, next1=3
return next1 = 3  OK

I left the Python version with two variables for clarity on the swap pattern. In Python the rolling-variable approach is ergonomically a bit noisier — you have to track which variable is i+1 and which is i+2 after the swap. At n <= 100 the memory difference is genuinely irrelevant. In C# I compress because the int array would be heap-allocated anyway, and the variable naming reads cleanly.

Time: O(n). Space: O(1).

Complexity comparison

All three are O(n) time — the memoization ensures no index is computed twice regardless of approach. The space difference is what matters in practice.

Edge cases worth knowing

These come up in interviews because they test whether you actually understood the guards:

• s = "0": s[0] == '0' kills the single-digit path immediately; no two-digit path exists since there's only one character. Returns 0. The code handles this because the s[i] != '0' check sets current = 0 and the loop returns next1 = 0.
• s = "10": i=1, s[1]='0' -> single-digit path dead, dp[1]=0. i=0, s[0]='1', single-digit -> current = dp[1] = 0. Two-digit "10" = 10 is in [10,26] -> current += dp[2] = 1. Returns 1. Only one decoding: "J". The '0' is absorbed by the leading '1'.
• s = "30": i=1, s[1]='0' -> 0. i=0, s[0]='3', single-digit -> current = 0. "30" = 30 > 26, no two-digit path. Returns 0. The '3' cannot rescue '0' because 30 exceeds the alphabet.
• s = "27": i=1, current = 1. i=0, single-digit -> current = 1. "27" = 27 > 26 -> no two-digit path. Returns 1. Only decoding: "B-G". This is the "just over the edge" case that catches off-by-one bugs in the range check.
• s = "11106": Three decodings: (1,1,10,6), (11,10,6). The grouping (1,11,06) is invalid because "06" is not in [10,26] — the two-digit gate blocks it. The code handles this naturally: when i=3 and s[3]='0', dp[3]=0, so any path that tries to route through a single '0' contributes 0.

The key insight: '0' is lethal. It kills the single-digit path at that position completely, and it can only be saved by a preceding '1' or '2' that forms a valid two-digit group ("10" or "20"). A '0' following anything else ("30", "40", ...) causes that entire branch to return 0.

What this adds to the pattern vocabulary

If Climbing Stairs is the template and Min Cost Climbing Stairs is "the template with weights," Decode Ways is "the template with gates that can zero out a path entirely." House Robber does something adjacent — you skip i+1 on purpose rather than being forced — but the structural shape is the same two-lookahead DP.

The gating is the new idea. If you replaced both guard conditions with true, the recurrence collapses to Climbing Stairs. Every valid path in the dp table exists only because both guards let it through. When a '0' appears, that entire branch silently returns 0 and contributes nothing upstream. When a two-digit slice exceeds 26, the second path just doesn't get added.

When you see a DP problem and ask yourself "is this Climbing Stairs?" — the right follow-up is "are the transitions gated?" If yes, you're here.

Related problems

Word Break (139) is the non-linear cousin. Instead of looking 1 or 2 steps ahead with simple range checks, you look up to the longest word in the dictionary. The gating logic is more expensive but the pattern is the same: at each position, can I consume k characters? Check the dictionary; if yes, inherit from dp[i+k].

Climbing Stairs (70) is the ungated version of this problem. Both transitions are always available. No '0' guard, no range check. If you can solve that, you understand the skeleton; Decode Ways just adds the gates.

Jump Game II (45) inverts the direction. Instead of counting paths, you're minimizing jumps. But "which positions can reach position i?" is structurally identical to "which suffixes can I decode from position i?"

Combination Sum IV (377) and Integer Break (343) both live in this neighborhood — fixed-base or arbitrary-base DP where each state accumulates from reachable predecessors, all with explicit validity conditions.

Once you've internalized the gated transition, you'll start seeing it everywhere. The guard conditions change; the shape stays.