LeetCode 91: Decode Ways Solution in Python Explained

Problem Statement

In LeetCode 91, you’re given a string s containing digits. Each digit (1-9) maps to a letter (A-I), and two-digit numbers (10-26) map to J-Z (0 alone isn’t valid). Your task is to return the number of possible decodings. This differs from subset generation like LeetCode 90: Subsets II, focusing on string interpretation.

Constraints

• 1 <= s.length <= 100
• s contains only digits (0-9)

Example

Let’s see some cases:

Copy codeInput: s = "12"
Output: 2
Explanation: "12" can be decoded as "AB" (1,2) or "L" (12) - 2 ways.

Copy codeInput: s = "226"
Output: 3
Explanation: "BBF" (2,2,6), "VF" (22,6), "BF" (2,26) - 3 ways.

Copy codeInput: s = "06"
Output: 0
Explanation: "06" can’t be decoded (0 isn’t valid alone, 06 isn’t 1-26).

These examples show we’re counting valid decoding combinations.

Understanding the Problem

How do you solve LeetCode 91: Decode Ways in Python? Take s = "226". We need to count ways: "BBF" (2,2,6), "VF" (22,6), "BF" (2,26) = 3. Each digit can be decoded alone (1-9) or paired (10-26), but 0 complicates things. This isn’t a binary sequence like LeetCode 89: Gray Code; it’s about dynamic string partitioning. We’ll use: 1. Dynamic Programming Bottom-Up: O(n) time, O(n) space—our top pick. 2. Recursive with Memoization: O(n) time, O(n) space—a recursive option.

Let’s dive into the primary solution.

Solution 1: Dynamic Programming Bottom-Up Approach (Primary)

Explanation

Use a DP array where dp[i] is the number of ways to decode s[0:i]. For each position, add ways from using the last digit (if valid) and the last two digits (if valid). Iterate left to right, building solutions based on previous results.

For s = "226":

• dp[0] = 1 (empty string).
• dp[1] = 1 ("2").
• dp[2] = 2 ("22" = "BB" or "V").
• dp[3] = 3 ("226" = "BBF", "VF", "BF").

Step-by-Step Example

Example 1: s = "226"

Goal: Return 3.

• Start: dp = [1,0,0,0] (length 4 for "226").
• Step 1: i = 1, s[0] = "2".
• Single digit (2): Valid, dp[1] += dp[0] = 1.
• dp = [1,1,0,0].
• Step 2: i = 2, s[1] = "2", s[0:2] = "22".
• Single (2): dp[2] += dp[1] = 1.
• Two-digit (22): Valid, dp[2] += dp[0] = 2.
• dp = [1,1,2,0].
• Step 3: i = 3, s[2] = "6", s[1:3] = "26".
• Single (6): dp[3] += dp[2] = 2.
• Two-digit (26): Valid, dp[3] += dp[1] = 3.
• dp = [1,1,2,3].
• Finish: Return dp[3] = 3.

Example 2: s = "12"

Goal: Return 2.

• Start: dp = [1,0,0].
• Step 1: i = 1, s[0] = "1".
• Single (1): dp[1] = 1.
• dp = [1,1,0].
• Step 2: i = 2, s[1] = "2", s[0:2] = "12".
• Single (2): dp[2] = 1.
• Two-digit (12): dp[2] = 2.
• dp = [1,1,2].
• Finish: Return 2.

Example 3: s = "06"

Goal: Return 0.

• Start: dp = [1,0,0].
• Step 1: i = 1, s[0] = "0".
• Single (0): Invalid, dp[1] = 0.
• dp = [1,0,0].
• Step 2: i = 2, s[1] = "6", s[0:2] = "06".
• Single (6): dp[2] = 0 (dp[1]=0).
• Two-digit (06): Invalid, dp[2] = 0.
• dp = [1,0,0].
• Finish: Return 0.

How the Code Works (Dynamic Programming Bottom-Up) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef numDecodings(s: str) -> int:
    # Line 1: Initialize DP array
    dp = [0] * (len(s) + 1)
    # Creates array of zeros with length s + 1 (e.g., [0,0,0,0] for "226")
    # dp[i] = ways to decode s[0:i], extra slot for empty string

    # Line 2: Base case for empty string
    dp[0] = 1
    # dp[0] = 1, represents an empty string having 1 way (no decoding)
    # Foundation for building up solutions

    # Line 3: Iterate over each position in the string
    for i in range(1, len(s) + 1):
        # i goes from 1 to len(s) (e.g., 1 to 3 for "226")
        # Each iteration computes ways to decode up to index i

        # Line 4: Check single-digit decoding
        if s[i-1] != '0':
            # If last digit isn’t '0' (e.g., s[0]='2'), it’s decodable (1-9)
            # Add ways from previous position

            # Line 5: Add ways using single digit
            dp[i] += dp[i-1]
            # Adds the number of ways to decode up to i-1 (e.g., dp[1] += dp[0] = 1)
            # If s[0]='2', "2" has 1 way, same as empty string plus "B"

        # Line 6: Check two-digit decoding
        if i > 1 and '10' <= s[i-2:i] <= '26':
            # If i > 1 (at least two digits) and s[i-2:i] is between "10" and "26"
            # e.g., i=2, s[0:2]="22" is valid (22 <= 26)

            # Line 7: Add ways using two digits
            dp[i] += dp[i-2]
            # Adds ways from two positions back (e.g., dp[2] += dp[0] = 1)
            # For "22", adds 1 way ("V") to existing 1 way ("BB"), total 2

    # Line 8: Return the total number of ways
    return dp[len(s)]
    # Returns dp[len(s)], ways to decode the entire string (e.g., dp[3] = 3 for "226")

This detailed explanation makes the bottom-up DP process clear, efficiently counting decodings.

Alternative: Recursive with Memoization Approach

Explanation

Recursively compute ways to decode from each position, using memoization to cache results. At each step, try single-digit and two-digit decodings if valid, summing the possibilities.

For "226":

• "2" + decode("26") = 2.
• "22" + decode("6") = 1.
• Total = 3.

Step-by-Step Example (Alternative)

For "226":

• decode(0): "2" + decode(1) = 2, "22" + decode(2) = 1 → 3.
• decode(1): "2" + decode(2) = 2.
• decode(2): "6" + decode(3) = 1.
• decode(3): 1 (empty).
• Finish: 3.

How the Code Works (Recursive)

Copy codedef numDecodingsRecursive(s: str) -> int:
    @lru_cache(None)
    def dp(i: int) -> int:
        if i == len(s):
            return 1
        if s[i] == '0':
            return 0
        ways = dp(i + 1)
        if i + 1 < len(s) and '10' <= s[i:i+2] <= '26':
            ways += dp(i + 2)
        return ways
    return dp(0)

Complexity

• DP Bottom-Up:
• Time: O(n) – single pass.
• Space: O(n) – DP array.
• Recursive with Memoization:
• Time: O(n) – memoized states.
• Space: O(n) – memoization cache.

Efficiency Notes

Both are O(n) time, but Bottom-Up avoids recursion overhead, making it slightly faster and more space-efficient—preferred for its clarity and performance.

Key Insights

• DP State: Ways up to each position.
• Zero Handling: Invalidates single-digit decoding.
• Two-Digit Check: 10-26 range.

Additional Example

For s = "123":

• Goal: 3.
• DP: "1,2,3", "12,3", "1,23" → 3.

Edge Cases

• Single Digit: "1" → 1.
• All Zeros: "0" → 0.
• Leading Zero: "06" → 0.

Both solutions handle these well.

Final Thoughts

LeetCode 91: Decode Ways in Python is a delightful string decoding puzzle. The Bottom-Up DP solution is efficient and intuitive, while Recursive with Memoization offers a top-down perspective. Want more? Try LeetCode 139: Word Break for string segmentation or LeetCode 90: Subsets II for combinatorics. Ready to practice? Solve LeetCode 91 on LeetCode with "226", aiming for 3—test your skills now!