LeetCode 91 Decode Ways - Implementation

Here is the implementation for Decode Ways (LeetCode $91$):

function numDecodings(s)
    n := length of s
    dp := array of size n + 1, all set to 0
    dp[n] := 1
    for i from n - 1 down to 0
        if s[i] = '0' then
            dp[i] := 0
        else
            dp[i] := dp[i + 1]
            if i + 1 < n then
                twoDigit := integer value of s[i..i+1]
                if twoDigit >= 10 and twoDigit <= 26 then
                    dp[i] := dp[i] + dp[i + 2]
    return dp[0]

The tricky part is handling '$0$' correctly. A '$0$' can never be decoded alone, so dp[i] stays $0$ when s[i] is '$0$'. For all other digits, you take dp[i+1] (one digit) and optionally add dp[i+2] if the two-digit number falls in $10$-$26$. Trace through "$226$" to verify: dp[3]=1, dp[2]=1, dp[1]=2, dp[0]=3.

Time complexity: $O(n)$.

Space complexity: $O(n)$, reducible to $O(1)$ by tracking only the last two values.