Dynamic Programming Solution for the Decode Ways Problem: A Complete Guide

The dynamic programming solution for the Decode Ways problem uses bottom-up tabulation to count valid alphabetic interpretations of a numeric string in O(n) time by tracking whether each single digit (1-9) or double-digit pair (10-26) forms a valid letter mapping.

The Decode Ways problem is a classic interview question that tests your ability to recognize overlapping subproblems and optimal substructure—hallmarks of dynamic programming. In the kdn251/interviews repository, you'll find a clean Java implementation that demonstrates exactly how to solve this LeetCode challenge using a systematic DP approach. This guide breaks down the dynamic programming solution for the Decode Ways problem, explaining the recurrence relation, base cases, and space optimizations used in the reference implementation.

Understanding the Decode Ways Problem

The problem asks you to determine the total number of ways to decode a numeric string where 'A' maps to 1, 'B' to 2, and 'Z' to 26. A valid decoding must parse the entire string without leading zeros—meaning '0' cannot stand alone, and two-digit numbers must fall within the 10-26 range to correspond to letters.

Dynamic Programming Approach and Recurrence Relation

The solution leverages the fact that the number of ways to decode a string starting at position i depends only on the solutions for positions i+1 and i+2. This creates a natural bottom-up dynamic programming structure.

Defining the DP State

Let dp[i] represent the number of ways to decode the substring s[i:], which is the suffix of the string starting at index i. The final answer we seek is dp[0], representing the number of ways to decode the entire string from the beginning.

Base Cases

The dynamic programming solution for the Decode Ways problem requires two base cases to terminate the recurrence:

• dp[n] = 1: An empty suffix (when we've processed the entire string) has exactly one valid decoding—the empty string itself.
• dp[n-1] = 1 if the last character is not '0', otherwise 0: A single non-zero digit always maps to one letter, but '0' cannot stand alone.

Transition Logic

For each position i from n-2 down to 0, apply the following rules as implemented in kdn251/interviews:

1. If s[i] == '0', set dp[i] = 0 because '0' cannot start a valid encoding.
2. Otherwise, start with dp[i] = dp[i+1] (decoding the current digit as a single letter).
3. If the two-digit number formed by s[i] and s[i+1] is between 10 and 26, add dp[i+2] to account for decoding these two digits as a single letter.

The formal recurrence is:

if s[i] == '0':
    dp[i] = 0
else:
    dp[i] = dp[i+1] + (10 <= value(s[i..i+1]) <= 26 ? dp[i+2] : 0)

Java Implementation from kdn251/interviews

The reference implementation in the kdn251/interviews repository follows exactly this dynamic programming approach. The numDecodings method in leetcode/string/DecodeWays.java and company/uber/DecodeWays.java implements the bottom-up solution with O(n) space:

public class DecodeWays {
    public int numDecodings(String s) {
        int n = s.length();

        if (n == 0) {
            return 0;
        }

        int[] dp = new int[n + 1];
        dp[n] = 1;                                   // empty suffix
        dp[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0; // last character

        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                continue;                            // dp[i] stays 0
            } else {
                int twoDigit = Integer.parseInt(s.substring(i, i + 2));
                dp[i] = (twoDigit <= 26) ? dp[i + 1] + dp[i + 2] : dp[i + 1];
            }
        }

        return dp[0];
    }
}

This implementation correctly handles edge cases such as leading zeros and invalid two-digit combinations while computing the total decode ways in a single reverse pass through the string.

Space Optimization to O(1)

As noted in the source analysis, the dynamic programming solution for the Decode Ways problem only requires the previous two states (dp[i+1] and dp[i+2]) to compute the current value. This allows reducing the space complexity from O(n) to O(1) by using two variables instead of an array:

public int numDecodingsOptimized(String s) {
    int n = s.length();
    if (n == 0) return 0;

    int a = 1; // dp[i+2]
    int b = s.charAt(n - 1) != '0' ? 1 : 0; // dp[i+1]

    for (int i = n - 2; i >= 0; i--) {
        int cur = 0;
        if (s.charAt(i) != '0') {
            cur = b;
            int two = Integer.parseInt(s.substring(i, i + 2));
            if (two <= 26) cur += a;
        }
        a = b;
        b = cur;
    }
    return b;
}

This optimized version maintains the same O(n) time complexity while using constant auxiliary space, making it ideal for memory-constrained environments or very large input strings.

Time and Space Complexity Analysis

The dynamic programming solution for the Decode Ways problem implemented in kdn251/interviews achieves optimal complexity bounds:

• Time Complexity: O(n), where n is the length of the input string. The algorithm performs a single reverse iteration through the string, performing O(1) work (character checks and integer parsing) at each position.
• Space Complexity: O(n) for the standard implementation using the dp array, or O(1) for the space-optimized variant that tracks only the last two states.

Both implementations handle all edge cases specified in the problem statement, including strings starting with '0', consecutive zeros, and invalid two-digit combinations greater than 26.

Summary

• The dynamic programming solution for the Decode Ways problem treats each position in the string as a subproblem depending only on the next one or two positions.
• The recurrence relation checks if the current digit (1-9) and potential two-digit number (10-26) form valid letter mappings, summing the ways from dp[i+1] and dp[i+2].
• The kdn251/interviews repository implements this in leetcode/string/DecodeWays.java and company/uber/DecodeWays.java using a bottom-up approach with O(n) time complexity.
• Space optimization reduces memory usage from O(n) to O(1) by maintaining only the previous two DP states.

Frequently Asked Questions

What is the base case for the Decode Ways dynamic programming solution?

The base cases occur at the end of the string. dp[n] (empty suffix) equals 1 because there is exactly one way to decode an empty string. dp[n-1] equals 1 if the last character is not '0' (mapping to a single letter), or 0 if it is '0' (invalid standalone digit). These base cases terminate the recurrence and allow the backward iteration to compute valid results for earlier positions.

Why does the dynamic programming solution iterate backwards through the string?

The algorithm iterates backwards (from n-2 down to 0) because the number of ways to decode the suffix starting at position i depends on the already-computed values for positions i+1 and i+2. This bottom-up approach ensures that subproblems are solved before they are needed by larger problems, avoiding the overhead of recursive calls and memoization while guaranteeing that dp[i+1] and dp[i+2] contain valid counts when computing dp[i].

How does the solution handle invalid inputs like "0" or "30"?

The solution handles '0' characters by checking if s[i] == '0' at each position. If true, dp[i] remains 0 because '0' cannot start a valid encoding. For two-digit numbers like "30", the algorithm checks if the value is ≤ 26; since 30 > 26, it does not add dp[i+2], effectively treating the '0' as invalid in that context and returning 0 ways for that path.

Can the Decode Ways dynamic programming solution be implemented recursively with memoization?

Yes, the dynamic programming solution can be implemented recursively using memoization (top-down DP). The recursive function would check the same conditions (single digit 1-9, double digit 10-26) and cache results for each index i to avoid recomputing subproblems. However, the bottom-up iterative approach shown in kdn251/interviews is generally preferred for its O(1) space optimization potential and avoidance of recursion stack overhead, which could cause stack overflow on very long strings.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}