LeetCode 91 - Decode Ways

This Medium problem asks for the number of ways to decode a string of digits. Each recursive step can consume either one digit or two, and memoization prevents different paths from recalculating the same suffix.

---

Problem link and explanation

• Problem: 91. Decode Ways
• Summary: Map the values 1 through 26 to A through Z and return the number of valid ways to decode the given digit string.

For example, 226 can be divided as 2-2-6, 22-6, or 2-26, giving three decodings. A zero cannot be decoded by itself. It is valid only as part of a two-digit value such as 10 or 20.

---

Approach

The recursive state is the current index. Reaching the end of the string completes one valid decoding, so that state returns 1. If the current character is zero, the current path is invalid and returns 0.

The one-digit branch advances by one position. The two-digit branch is available only when the substring beginning at the current index has a value from 10 through 26.

ways = self.decode(s, idx + 1, memo)

if idx + 2 <= len(s):
    num = int(s[idx:idx + 2])
    if 10 <= num <= 26:
        ways += self.decode(s, idx + 2, memo)

Different decoding paths can arrive at the same index, and every suffix beginning there has the same answer. Saving the result in memo[idx] makes each index a one-time computation.

---

Troubleshooting

Zero handling defines most of the edge cases. Without rejecting a path whose current character is zero, an invalid substring such as 06 could be treated as separate digits. Reaching idx == len(s) is different: it means the entire string was consumed successfully and must contribute one decoding.

The end-of-string check also has to run before accessing s[idx], otherwise the successful terminal state would attempt to read beyond the string.

---

Complexity analysis

• Time complexity: O(n)
  • Memoization computes the answer for each string index once.
• Space complexity: O(n)
  • The memo array and the recursion stack can both grow with the string length.

---

Implementation code

from typing import List

class Solution:
    def decode(self, s: str, idx: int, memo: List[int]) -> int:
        if idx == len(s):
            return 1
        if idx > len(s):
            return 0
        if int(s[idx]) == 0:
            return 0

        if memo[idx] != -1:
            return memo[idx]

        ways = self.decode(s, idx + 1, memo)

        if idx + 2 <= len(s):
            num = int(s[idx:idx + 2])
            if 10 <= num <= 26:
                ways += self.decode(s, idx + 2, memo)

        memo[idx] = ways
        return ways

    def numDecodings(self, s: str) -> int:
        memo = [-1] * len(s)
        return self.decode(s, 0, memo)

---

Summary and reflection

The recursion is a direct choice between consuming one digit and consuming two. The important constraints are that zero cannot stand alone and that a two-digit value must remain between 10 and 26. Since the current index completely determines the remaining work, memoization reduces the repeated recursion to linear time.