Decode Ways

Approach Summary

dp[i] = ways to decode s[0..i). Single digit: valid if not "0". Two digits: valid if in 10-26 range.

Full Solution & Approach

A digit string maps to letters where 1-26 are valid codes, and a leading zero is never a valid single-digit code. Let dp[i] be the number of ways to decode s[0..i), with dp[0] = 1. The last character alone is a valid decoding only if it is not "0", contributing dp[i-1] ways. The last two characters are valid only if they form a number from 10 to 26, contributing dp[i-2] ways. So dp[i] = (valid single digit ? dp[i-1] : 0) + (valid two digits ? dp[i-2] : 0). Because the recurrence only reads the previous two values, collapse the array into two rolling variables. The trap most people hit is "0": a zero can never be decoded alone and can only appear in 10 or 20, so the answer naturally becomes 0 for impossible strings like "30".

One pass with constant work per character — O(n) time. Two rolling variables — O(1) space.

Solution Code

Solution

def num_decodings(s: str) -> int:
    if not s or s[0] == '0':
        return 0
    prev2, prev1 = 1, 1  # ways for empty prefix and first char
    for i in range(1, len(s)):
        cur = 0
        if s[i] != '0':
            cur += prev1
        if 10 <= int(s[i - 1:i + 1]) <= 26:
            cur += prev2
        prev2, prev1 = prev1, cur
    return prev1

function numDecodings(s) {
  if (!s || s[0] === '0') return 0;
  let prev2 = 1, prev1 = 1;
  for (let i = 1; i < s.length; i++) {
    let cur = 0;
    if (s[i] !== '0') cur += prev1;
    const two = Number(s.slice(i - 1, i + 1));
    if (two >= 10 && two <= 26) cur += prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

public int numDecodings(String s) {
    if (s.isEmpty() || s.charAt(0) == '0') return 0;
    int prev2 = 1, prev1 = 1;
    for (int i = 1; i < s.length(); i++) {
        int cur = 0;
        if (s.charAt(i) != '0') cur += prev1;
        int two = Integer.parseInt(s.substring(i - 1, i + 1));
        if (two >= 10 && two <= 26) cur += prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int numDecodings(const string& s) {
    if (s.empty() || s[0] == '0') return 0;
    int prev2 = 1, prev1 = 1;
    for (int i = 1; i < (int)s.size(); i++) {
        int cur = 0;
        if (s[i] != '0') cur += prev1;
        int two = stoi(s.substr(i - 1, 2));
        if (two >= 10 && two <= 26) cur += prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Edge Cases to Watch

Leading zero — no valid decoding, return 0
A zero not preceded by 1 or 2 — return 0
Empty string — return 1 per convention
A single non-zero digit — return 1

How to Recognize This Pattern

Number of ways to decode digit string
Leading zero constraint

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)