Decode Ways

Recurse from the front: ways(i) is the number of ways to decode the remaining suffix s[i:]. From position i, take one digit (if it is nonzero) and/or two digits (if that two-digit number is at most 26), recursing on what is left.

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

Without memoization this branches like Fibonacci, recomputing the same suffixes repeatedly → exponential. With memoization there are only n distinct starting positions, each solved once in O(1) work beyond its (memoized) recursive calls → O(n) time. The memo dict and recursion depth cost O(n) space.

Build dp[i] left to right: the number of ways to decode the prefix s[0:i]. dp[0] = 1 (the empty prefix has exactly one, trivial, decoding). Then for each i, add dp[i-1] if the last single digit s[i-1] is valid, and add dp[i-2] if the last two digits s[i-2:i] form a valid code.

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

Trace for s = "226": every loop iteration asks the same two questions — is the last single digit a valid code, and is the last two-digit number in 10..26 — and adds the matching earlier dp value.

One pass filling n cells, O(1) work per cell → O(n) time, O(n) space for the dp array (which could be collapsed to two rolling variables for O(1) space, since each cell only needs the previous two).