Problem Description

You need to decode a secret message that's encoded as a string of numbers. The decoding uses this mapping:

• "1" → 'A'
• "2" → 'B'
• ...
• "25" → 'Y'
• "26" → 'Z'

The challenge is that a string of numbers can be decoded in multiple ways because some codes overlap. For instance, "25" could be interpreted as either "2" and "5" (giving 'BE') or as "25" (giving 'Y').

Given a string s containing only digits, you need to find the total number of ways to decode it.

Key rules:

• Leading zeros are not valid (e.g., "06" is invalid, only "6" is valid)
• The valid code range is from "1" to "26"
• If the string cannot be decoded in any valid way, return 0

Example with "11106":

• One way: (1, 1, 10, 6) → "AAJF"
• Another way: (11, 10, 6) → "KJF"
• Invalid: (1, 11, 06) because "06" starts with zero

The solution uses dynamic programming where f[i] represents the number of ways to decode the first i characters. For each position, we check:

1. If the current digit alone forms a valid code (1-9)
2. If the current digit combined with the previous one forms a valid code (10-26)

Intuition

Think of this problem as making choices while walking through the string from left to right. At each position, you face a decision: take one digit or take two digits together?

Imagine you're at position i in the string. The number of ways to decode up to this point depends on the choices you made earlier. This suggests a dynamic programming approach where we build up the solution incrementally.

The key insight is that to decode up to position i, you only have two possible last actions:

1. You decoded the digit at position i by itself (as a single-digit code 1-9)
2. You decoded positions i-1 and i together (as a two-digit code 10-26)

This means the number of ways to decode up to position i equals:

• The number of ways to decode up to position i-1 (if we can use digit i alone), plus
• The number of ways to decode up to position i-2 (if we can use digits i-1 and i together)

Why does this work? Because these represent completely separate, non-overlapping choices. If you choose to decode position i alone, you must have already decoded everything up to i-1. If you choose to decode positions i-1 and i together, you must have already decoded everything up to i-2.

This recursive relationship naturally leads to a bottom-up dynamic programming solution where f[i] stores the number of ways to decode the first i characters. We start with f[0] = 1 (empty string has one way to decode - doing nothing) and build up our answer step by step.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the dynamic programming approach using an array f where f[i] represents the number of ways to decode the first i characters of the string.

Initialization:

• Create array f of size n+1 where n = len(s)
• Set f[0] = 1 (base case: empty string has one way to decode)
• All other positions start at 0

Transition Logic: For each position i from 1 to n, we examine the corresponding character s[i-1] and update f[i] based on two conditions:

1. Single digit decoding: If the current character c is not '0', it can form a valid code by itself (1-9). In this case, we add the number of ways to decode up to the previous position:

   if c != "0":
       f[i] = f[i - 1]

2. Two digit decoding: If we can combine the previous character with the current one to form a valid code (10-26), we add the number of ways to decode up to position i-2:

   • Check if i > 1 (we need at least 2 characters)
   • Check if the previous character is not '0' (no leading zeros)
   • Check if the two-character substring s[i-2:i] forms a number ≤ 26

   if i > 1 and s[i - 2] != "0" and int(s[i - 2 : i]) <= 26:
       f[i] += f[i - 2]

Why this works:

• If a position starts with '0', it cannot be decoded alone, so we don't add f[i-1]
• Valid two-digit codes range from "10" to "26", which is why we check both the leading zero condition and the value constraint
• The final answer is f[n], representing the total ways to decode all n characters

Time Complexity: O(n) - we iterate through the string once
Space Complexity: O(n) - we use an array of size n+1

Example Walkthrough

Let's walk through the string "226" step by step to see how the dynamic programming solution works.

Setup:

• String: "226", length n = 3
• Create array f of size 4: f = [0, 0, 0, 0]
• Initialize f[0] = 1: f = [1, 0, 0, 0]

Step 1: Process first character '2' (i = 1)

• Current character c = '2'
• Check single digit: '2' != '0', so we can decode it as 'B'
  • f[1] = f[0] = 1
• Check two digits: i = 1, so we can't look back two positions
• Result: f = [1, 1, 0, 0]
• Meaning: There's 1 way to decode "2" → "B"

Step 2: Process second character '2' (i = 2)

• Current character c = '2'
• Check single digit: '2' != '0', so we can decode it alone
  • f[2] = f[1] = 1
• Check two digits: Previous char is '2', substring is "22"
  • '2' != '0' ✓ (no leading zero)
  • 22 <= 26 ✓ (valid code)
  • f[2] += f[0] = 1 + 1 = 2
• Result: f = [1, 1, 2, 0]
• Meaning: There are 2 ways to decode "22":
  • (2, 2) → "BB"
  • (22) → "V"

Step 3: Process third character '6' (i = 3)

• Current character c = '6'
• Check single digit: '6' != '0', so we can decode it alone
  • f[3] = f[2] = 2
• Check two digits: Previous char is '2', substring is "26"
  • '2' != '0' ✓ (no leading zero)
  • 26 <= 26 ✓ (valid code)
  • f[3] += f[1] = 2 + 1 = 3
• Result: f = [1, 1, 2, 3]
• Meaning: There are 3 ways to decode "226":
  • (2, 2, 6) → "BBF"
  • (22, 6) → "VF"
  • (2, 26) → "BZ"

Final Answer: f[3] = 3

The key insight is that at each position, we're building upon previously computed results. When we can form a valid two-digit code, we essentially create a "branch" in our decoding tree by adding the ways from two positions back.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the string s exactly once using a for loop that runs from index 1 to n (where n is the length of the string). Within each iteration, all operations are constant time:

• Checking if c != "0" is O(1)
• Accessing array elements f[i-1] and f[i-2] is O(1)
• String slicing s[i-2:i] creates a substring of at most 2 characters, which is O(1)
• Converting the substring to integer and comparison is O(1)

Therefore, the overall time complexity is O(n).

Space Complexity: O(n)

The algorithm uses an array f of size n + 1 to store the dynamic programming states. This array stores the number of ways to decode the string up to each position. No other data structures that scale with input size are used. The space for variables like i, c, and temporary substring operations use constant space.

Therefore, the overall space complexity is O(n), where n is the length of the input string.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors with Index Mapping

A frequent mistake occurs when confusing the DP array indices with string indices. Since dp[i] represents the number of ways to decode the first i characters, the corresponding string character is at s[i-1], not s[i].

Incorrect:

# Wrong: using s[i] instead of s[i-1]
if s[i] != '0':
    dp[i] = dp[i - 1]

Correct:

# Right: properly mapping dp index to string index
if s[i - 1] != '0':
    dp[i] = dp[i - 1]

2. Improper Handling of Leading Zeros

The condition s[i-2] != '0' is crucial but often forgotten. Without it, invalid codes like "06" would be counted as valid.

Incorrect:

# Wrong: only checking the upper bound
if i >= 2 and int(s[i - 2:i]) <= 26:
    dp[i] += dp[i - 2]

Correct:

# Right: ensuring no leading zeros AND within valid range
if i >= 2 and s[i - 2] != '0' and int(s[i - 2:i]) <= 26:
    dp[i] += dp[i - 2]

3. Not Handling Edge Cases Early

Strings starting with '0' or containing "00" will always have zero valid decodings. Failing to handle these cases can lead to unnecessary computation.

Enhanced Solution:

# Early termination for impossible cases
if s[0] == '0':
    return 0

# During iteration, if dp[i] remains 0, the string is undecodable
for i in range(1, n + 1):
    # ... existing logic ...
  
    # Early termination optimization
    if dp[i] == 0:
        return 0

4. Space Optimization Overlooked

Since each state only depends on the previous two states, using an array of size n+1 is unnecessary. This can be optimized to use only two variables.

Space-Optimized Version:

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