LeetCode 91: Decode Ways

Problem Description

LeetCode Problem 91

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

“1” -> ‘A’
“2” -> ‘B’
…
“25” -> ‘Y’
“26” -> ‘Z’

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes (“2” and “5” vs “25”).

For example, “11106” can be decoded into:

• “AAJF” with the grouping (1, 1, 10, 6)
• “KJF” with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because “06” is not a valid code (only “6” is valid).

Note: there may be strings that are impossible to decode. Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

Difficulty: Medium

Tags: string, dynamic programming

Rating: 72.75%

The Dynamic Programming Approach

1. Understanding the Subproblem

For any position in the string, we want to know how many ways we can decode the rest of the string starting from that position. This suggests our subproblem:

dp[i] = number of ways to decode the string from index i to the end

However, in our implementation, we use a slightly different but equivalent formulation: dp[i] = number of ways to decode the first i characters of the string

This second formulation turns out to be more convenient to implement.

2. Building the Recurrence Relation

At each position i, we have two possible operations:

1. Take one digit if it’s valid (1-9)

   • If s[i] is valid, we can decode it alone and add dp[i-1] ways
   • A single ‘0’ is not valid by itself

2. Take two digits if they form a valid letter (10-26)

   • If s[i-1:i+1] forms a valid two-digit number, we can add dp[i-2] ways
   • Numbers 27-99 and 00-09 are not valid

Therefore, our recurrence relation is:

dp[i] = (dp[i-1] if one_digit is valid) + (dp[i-2] if two_digits is valid)

3. Base Cases

We need two base cases:

• dp[0] = 1 (empty string can be decoded in one way)
• dp[1] = 1 if first digit is not ‘0’, else 0

4. Implementation Details

Let’s go through the solution code with detailed explanations:

def numDecodings(self, s: str) -> int:
    # Handle edge cases
    if not s or s[0] == '0': 
        return 0
    
    n = len(s)
    # dp[i] represents ways to decode first i characters
    dp = [0] * (n+1)
    
    # Base cases
    dp[0] = 1  # Empty string
    dp[1] = 1  # First character (we already checked it's not '0')
    
    for i in range(2, n+1):
        # Check if single digit is valid
        one_digit = int(s[i-1])
        if one_digit > 0:
            dp[i] += dp[i-1]
        
        # Check if two digits are valid
        two_digits = int(s[i-2:i])
        if 10 <= two_digits <= 26:
            dp[i] += dp[i-2]

The implementation uses an array where dp[i] represents the number of ways to decode the first i characters. We build this array iteratively, considering both one-digit and two-digit possibilities at each step.

Example Walkthrough

Let’s see how this works with the example “226”:

1. Initialize:

   • dp[0] = 1 (empty string)
   • dp[1] = 1 (just “2”)

2. For i = 2 (considering “22”):

   • One digit: “2” is valid → dp[2] += dp[1] = 1
   • Two digits: “22” is valid → dp[2] += dp[0] = 1
   • dp[2] = 2 total ways

3. For i = 3 (considering “226”):

   • One digit: “6” is valid → dp[3] += dp[2] = 2
   • Two digits: “26” is valid → dp[3] += dp[1] = 1
   • dp[3] = 3 total ways

Final decodings:

1. 2,2,6 → B,B,F
2. 2,26 → B,Z
3. 22,6 → V,F

Optimization Opportunities

The current solution uses O(n) space, but we can optimize it to O(1) space since we only need the last two values at any point. Here’s how the space-optimized version would look:

def numDecodings(self, s: str) -> int:
    if not s or s[0] == '0':
        return 0
        
    two_back = 1  # dp[i-2]
    one_back = 1  # dp[i-1]
    current = one_back  # dp[i]
    
    for i in range(1, len(s)):
        current = 0
        if s[i] != '0':
            current += one_back
        if 10 <= int(s[i-1:i+1]) <= 26:
            current += two_back
            
        two_back = one_back
        one_back = current
    
    return current

This version maintains the same logic but only keeps track of three variables instead of an array, reducing space complexity to O(1).