Decode Ways

How it works

This is the space-optimized version of bottom-up DP.

From the bottom-up approach, we know:

• dp[i] depends only on dp[i+1] and dp[i+2]
• So we don’t need an entire DP array

We just keep:

• dp1 → ways to decode from i + 1
• dp2 → ways to decode from i + 2

At each index i, we compute the current answer using these two values, then shift them forward.

Steps

1. Initialize:
   • dp1 = 1 → corresponds to dp[len(s)]
   • dp2 = 0
2. Iterate from right to left:
   • If s[i] == '0' → current ways = 0
   • Else:
     • Start with dp1 (take one digit)
     • If two digits form a valid number (10-26), add dp2
3. After computing current:
   • Shift values:
     • dp2 = dp1
     • dp1 = current
4. Return dp1

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Not Handling Leading Zeros

A string starting with '0' or containing '0' that cannot pair with the previous digit has zero valid decodings. This is the most common edge case to miss.

Incorrect Two-Digit Validation

Two digits form a valid decoding only if they represent 10-26. Common mistakes include allowing "00", "07", or values above 26.

Confusing Base Case Value

When the entire string is decoded (index reaches the end), there is exactly 1 valid decoding (the one that got us here). Returning 0 instead causes all paths to count as zero.

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = dp2 = 0
        dp1 = 1
        for i in range(len(s) - 1, -1, -1):
            if s[i] == "0":
                dp = 0
            else:
                dp = dp1

            if i + 1 < len(s) and (s[i] == "1" or
               s[i] == "2" and s[i + 1] in "0123456"
            ):
                dp += dp2
            dp, dp1, dp2 = 0, dp, dp1
        return dp1

class Solution {
public:
    int numDecodings(string s) {
        int dp = 0, dp2 = 0;
        int dp1 = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp = 0;
            } else {
                dp = dp1;
                if (i + 1 < s.size() && (s[i] == '1' ||
                    s[i] == '2' && s[i + 1] < '7')) {
                    dp += dp2;
                }
            }
            dp2 = dp1;
            dp1 = dp;
            dp = 0;
        }
        return dp1;
    }
};