Chapter 13: Conditional Transitions - Decode Ways

Having explored problems involving string segmentation and reconstruction, we now return to the fundamental DP pattern of counting permutations. We'll examine a problem that resembles "Climbing Stairs" but introduces a crucial new element: the transitions between states are conditional, depending on the input data itself.

This problem is "Decode Ways" (LeetCode #91). We are asked to count the number of ways a string of digits can be decoded into a sequence of letters. The rules for decoding make this a perfect dynamic programming problem, as the number of ways to decode a string depends on the ways its prefixes can be decoded.

The Problem:

A message containing letters from A-Z is being encoded into numbers using the following mapping: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above. There may be multiple ways to group the digits.

For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)

• "KJF" with the grouping (11 10 6)

It cannot be mapped into "AKF" with the grouping (1 11 06) because "06" is not a valid mapping.

Given a string s containing only digits, return the number of ways to decode it.

Approach 1: The Recursive Solution

Let's define a function solve(i) that returns the number of ways to decode the suffix s[i:].

At any index i, we have two main possibilities for our next step:

1. Decode a single digit: We can decode the character s[i] as a single letter. This is only possible if s[i] is not '0'. If it's valid, we add the number of ways to decode the rest of the string, which is solve(i + 1).

2. Decode two digits: We can decode the characters s[i:i+2] as a single letter. This is only possible if the two-digit number is between 10 and 26, inclusive. If it's valid, we add the number of ways to decode the rest of the string, which is solve(i + 2).

The base case is when i reaches the end of the string. This represents one successful decoding, so we return 1.

def numDecodings_recursive(s: str) -> int:

    def solve(i):
        # Base case: A completed decoding counts as one way.
        if i >= len(s):
            return 1

        # A '0' cannot be the start of a letter.
        if s[i] == '0':
            return 0

        # Decode the current digit as a single letter
        ways = solve(i + 1)

        # Try to decode the current and next digit as a two-digit letter
        if i + 1 < len(s) and int(s[i:i+2]) <= 26:
            ways += solve(i + 2)

        return ways

    return solve(0)

# Trying it out
# print(numDecodings_recursive("226")) # 3 -> "BBE", "BZ", "VF"
# print(numDecodings_recursive("12"))   # 2 -> "AB", "L"
# print(numDecodings_recursive("06"))   # 0 -> Invalid
# print(numDecodings_recursive("2101")) # Very slow on long inputs

This brute-force recursion correctly explores all paths but suffers from the same overlapping subproblems we've seen before.

Approach 2: Memoization with a Decorator (Top-Down DP)

The recursive state is defined only by the index i, making it a perfect candidate for our caching decorator. This will eliminate redundant calculations and make the solution efficient.

import functools

class Solution:
    def numDecodings_memoized(self, s: str) -> int:

        @functools.lru_cache(maxsize=None)
        def solve(i):
            if i >= len(s):
                return 1

            if s[i] == '0':
                return 0

            ways = solve(i + 1)

            if i + 1 < len(s) and int(s[i:i+2]) <= 26:
                ways += solve(i + 2)

            return ways

        return solve(0)

# Trying it out
# solver = Solution()
# print(solver.numDecodings_memoized("210121012101")) # Fast!

The logic remains identical to the recursive approach, but its performance is now O(n), where n is the length of the string, as each subproblem solve(i) is computed only once.

Approach 3: Iteration (Bottom-Up DP)

We can solve this iteratively using a dp array where dp[i] stores the number of ways to decode the prefix s[:i].

1. Create a dp array of size n+1.

2. Initialize dp[0] = 1 (one way to decode an empty string) and dp[1] = 0 if s[0] == '0' else 1.

3. Iterate i from 2 to n. At each step i, we calculate dp[i]:

   • One-digit move: Look at the (i-1)th character of s. If s[i-1] is not '0', we can form a valid decoding by appending it to all decodings of s[:i-1]. So, we add dp[i-1] to dp[i].

   • Two-digit move: Look at the substring s[i-2:i]. If this forms a number between 10 and 26, we can form a valid decoding by appending it to all decodings of s[:i-2]. So, we add dp[i-2] to dp[i].

4. The final answer is dp[n].

def numDecodings_iterative(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 0 if s[0] == '0' else 1

    for i in range(2, n + 1):
        # One-digit move
        one_digit = int(s[i-1:i])
        if one_digit >= 1:
            dp[i] += dp[i-1]

        # Two-digit move
        two_digits = int(s[i-2:i])
        if 10 <= two_digits <= 26:
            dp[i] += dp[i-2]

    return dp[n]

# Trying it out
# print(numDecodings_iterative("226")) # 3

This bottom-up solution is highly efficient in both time (O(n)) and space. In fact, since dp[i] only depends on dp[i-1] and dp[i-2], you can optimize the space further to O(1) by only storing the last two values, just like in the "Climbing Stairs" problem.

Conclusion

"Decode Ways" is a fantastic problem that reinforces the core of 1D dynamic programming. It shows how the simple "Fibonacci-style" recurrence, where the solution at i depends on solutions at i-1 and i-2, can be adapted to handle complex conditions. The key takeaway is recognizing that while the structure is familiar, the transitions themselves can be governed by the specific values within the input data, adding a rich layer of logic to the problem.