Problem Statement

Given a string containing only digits, count the number of ways to decode it into letters, where '1' maps to 'A', '2' maps to 'B', ..., '26' maps to 'Z'. A valid single digit must be between '1' and '9', while a valid pair must form a number between 10 and 26.

State Definition

Define dp[i] as the total number of valid decodings for the substring ending at position i. This state captures all possible ways to decode the prefix up to index i.

State Transition

At each position i, decoding can happen in two ways:

Single digit decoding: When s[i] represents a valid single digit (1-9), it can be decoded independently. This contributes dp[i-1] ways:

dp[i] += dp[i-1]  if s[i] != '0'

Two-digit decoding: When the two-digit number formed by s[i-1] and s[i] falls between 10 and 26 (and s[i-1] != '0'), they can be decoded together. This contributes dp[i-2] ways:

dp[i] += dp[i-2]  if 10 <= (s[i-1]*10 + s[i]) <= 26

Initialization

Two initialization strategies exist to handle boundary conditions:

Approach 1: Initialize both dp[0] and dp[1] explicitly. Check the first character and the first two characters separately, then iterate from index 2.

Approach 2: Extend the dp array by one element (n+1), initializing dp[0] = 1 as a sentinel value. This allows the loop to start from index 2 with consistent indexing, where dp[i] corresponds to the first i characters.

Table Filling Order

Process the string from left to right, computing each state based on previously computed values.

Return Value

• Approach 1 returns dp[n-1] (n-th element, 0-indexed)
• Approach 2 returns dp[n] (n+1 sized array, so n is the n-th character)

Implementation

Appproach 1: Explicit two-element initialization

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        int[] memo = new int[len];
        char[] chars = s.toCharArray();

        if (chars[0] != '0') {
            memo[0] = 1;
        }

        if (len == 1) {
            return memo[0];
        }

        if (chars[1] != '0') {
            memo[1] += memo[0];
        }

        int combined = (chars[0] - '0') * 10 + chars[1] - '0';
        if (combined >= 10 && combined <= 26) {
            memo[1] += 1;
        }

        for (int i = 2; i < len; i++) {
            if (chars[i] != '0') {
                memo[i] += memo[i - 1];
            }
            combined = (chars[i - 1] - '0') * 10 + chars[i] - '0';
            if (combined >= 10 && combined <= 26) {
                memo[i] += memo[i - 2];
            }
        }

        return memo[len - 1];
    }
}

Approach 2: Sentinel value initialization

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        int[] memo = new int[len + 1];
        char[] chars = s.toCharArray();
        
        memo[0] = 1;
        if (chars[0] != '0') {
            memo[1] = 1;
        }

        for (int i = 2; i <= len; i++) {
            int single = chars[i - 1] - '0';
            if (single != 0) {
                memo[i] += memo[i - 1];
            }
            
            int pair = (chars[i - 2] - '0') * 10 + single;
            if (pair >= 10 && pair <= 26) {
                memo[i] += memo[i - 2];
            }
        }

        return memo[len];
    }
}

Complexity Analysis

• Time complexity: O(n) — single pass through the string
• Space complexity: O(n) — dp array of size n or n+1