Domain 2MediumCORE

Decode Ways

The goal is to count how many distinct ways we can partition the input string s into valid numeric chunks, where each chunk maps back to a letter 'A' through 'Z'. The mapping rules are: single digits '1'-'9', and two-digit numbers '10'-'26'.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String#Dynamic Programming

91. Decode Ways

Model: qwen3.5:9b
Topics: String,Dynamic Programming
FAANG asked: 1
Acceptance rate: 26.9%


Problem Breakdown

The goal is to count how many distinct ways we can partition the input string s into valid numeric chunks, where each chunk maps back to a letter ‘A’ through ‘Z’. The mapping rules are: single digits “1”-“9”, and two-digit numbers “10”-“26”.

Key Constraints & Edge Cases:

  • Leading Zeros: A number cannot start with 0 (e.g., “06” is invalid, but “10” or “20” are valid). If the string starts with ‘0’, there are zero ways.
  • Invalid Digits: Any single digit chunk must be between ‘1’ and ‘9’. A ‘0’ cannot stand alone as a letter.
  • Input Size: Length up to 100, which suggests an O(N)O(N) or O(N2)O(N^2) solution is acceptable, but we aim for optimal efficiency.

Intuition

Initially, I might consider using recursion with backtracking: at each step, try taking one digit (if valid) and recurse on the rest of the string, then try taking two digits (if valid) and recurse again. However, this leads to overlapping subproblems where we recompute the number of ways for the same suffix multiple times. This results in exponential time complexity O(2N)O(2^N), which will timeout given constraints like s.length = 100.

The key insight is that the problem exhibits optimal substructure and overlapping subproperties. The decision at index i only depends on whether we take one digit or two digits ending at i, combined with how many ways existed to decode up to i-1 (or i-2). This structure strongly suggests Dynamic Programming, where we build the solution iteratively from left to right.

Approach

I will use a 1D DP array of size N+1N+1, where dp[i] represents the number of ways to decode the substring ending at index i-1.

  • Base Case: An empty string has one way (do nothing), so dp[0] = 1.
  • Iteration: Iterate from i = 1 to N. At each step, consider two possibilities:
    1. Single Digit: If the current character s[i-1] is not ‘0’, we can treat it as a single letter (A-J). We add dp[i-1] ways.
    2. Two Digits: If there are at least two characters remaining (i >= 2) and they form a valid number between “10” and “26”, we add the ways from dp[i-2]. Crucially, this pair must not start with ‘0’ (e.g., “05” is invalid).
  • Result: The value at dp[N] will hold the total count.

Complexity Analysis

  • Time Complexity: O(N)O(N) where N is the length of string s. We iterate through the string exactly once, performing constant time checks for each index.
  • Space Complexity: O(N)O(N) to store the DP array. This can be optimized to O(1)O(1) space by only tracking the last two values (dp[i-1] and dp[i-2]) instead of the full array, but given N=100, an array is clearer for readability without significant overhead.

Solution

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        # dp[i] represents number of ways to decode substring s[0...i-1]
        dp = [0] * (n + 1)
        
        # Base case: empty string has one way (do nothing)
        dp[0] = 1
        
        for i in range(1, n + 1):
            current_char = s[i - 1]
            
            # Check single digit decoding ('A'-'J')
            if current_char != '0':
                dp[i] += dp[i - 1]
                
            # Check two-digit decoding ('K'-'Z', i.e., "10"-"26")
            if i >= 2:
                prev_two = s[i - 2:i]
                # Must not start with '0' and must be <= 26
                if int(prev_two) > 0 and int(prev_two) <= 26:
                    dp[i] += dp[i - 2]

        return dp[n]

Edge Cases Handled

  • Leading Zero in String: If s starts with ‘0’ (e.g., “0”, “01”), the single digit check fails for index 1, and the two-digit check will fail because any pair starting at index -2 would include that leading zero. The code correctly returns 0.
  • Invalid Two-Digit Numbers: If a substring like “37” or “59” appears, int(prev_two) <= 26 ensures it is not counted as valid decoding for the two-digit case.
  • Zero in Middle/End (e.g., “10”, “101”): The single digit check explicitly skips if current_char == '0'. This forces reliance on a preceding non-zero digit to form a valid 2-digit number like “10” or “20”.
  • Single Character: If N=1, the loop runs once. If char is not ‘0’, returns 1; else returns 0.