91. Decode Ways

Problem¶

Given a digit string, count its valid partitions into codes from "1" through "26"; codes cannot have leading zeros.

s = "226" -> ["2|2|6", "2|26", "22|6"] -> 3

Key trick¶

Use dynamic programming: the ways to decode each prefix equal the ways before its last digit, if valid, plus the ways before its last two digits, if valid.

Trap¶

"0" cannot be decoded alone.
Two-digit codes must be between "10" and "26".
A valid local choice may still lead to an invalid full decoding, so greedy decoding fails.
Initialize the empty prefix with one way so valid two-digit prefixes are counted.

Why is it interesting?¶

It reduces an exponential partition search to a Fibonacci-like recurrence while requiring careful handling of zeros and DP initialization.

Python solution¶

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0":
            return 0

        # prev2: ways to decode the prefix ending two positions earlier.
        # prev1: ways to decode the prefix ending one position earlier.
        prev2 = prev1 = 1

        for i in range(1, len(s)):
            cur = 0

            if s[i] != "0":
                cur += prev1

            if "10" <= s[i - 1:i + 1] <= "26":
                cur += prev2

            prev2, prev1 = prev1, cur

        return prev1

Time complexity: \(O(n)\).

Space complexity: \(O(1)\).

Comment on my solution¶

Your solution is correct and already achieves \(O(n)\) time and \(O(1)\) space.

The rolling DP state is initialized and updated correctly, including after an invalid prefix such as "0".
The valid set works, but constructing 26 strings is unnecessary; direct checks for a nonzero digit and a two-digit range are clearer.
The comments incorrectly suggest that a simple dp[i] is insufficient: this problem directly supports prefix DP because every decoding ending at position i uses either one or two final digits.
Names such as prev1 and prev2 could be clarified with comments describing which prefix each represents.

# WORKS
class Solution:
    def numDecodings(self, s: str) -> int:
        # "11106" -> 2
        # "AAJF" (1, 1, 10, 6)
        # "KJF" (11, 10, 6)
        # (1,11,06) invalid because 06 is invalid
        #
        # "06" -> 0 (because it can't be decoded)
        #
        # - backtraking on s with pruning when a group of 1 or 2
        #   number characters can't be decoded
        # - DP
        #   - difficulty comes from grouping 1 or 2 character before decoding
        #     so we can't have a simple dp[i] where i the index in s
        #     - and we don't know until consuming until the end if the
        #       decomposition is correct.
        #     - maybe we can start from the end a go backward
        #     - dp[i] = valid decomposition ending a i in s
        #             = (dp[i - 1] if letter at i is valid) +
        #             + (dp[i - 2] if combination of letter at i - 1 and i valid)

        # alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        # decode = {str(ord(ch) - ord("A") + 1): ch for ch in alphabet}

        valid = {str(x) for x in range(1,27)}

        prev1 = 1
        prev2 = 1

        for i in range(len(s)):
            total = 0
            if s[i] in valid:
                total += prev1
            if i > 0 and s[i-1:i+1] in valid:
                total += prev2
            prev2 = prev1
            prev1 = total

        return prev1