Problem statement

A message of letters A–Z is encoded with A=1, B=2, … Z=26 and you receive only the digit string s. Return the number of ways to decode it (grouping digits into valid codes 1–26; codes with leading zeros are invalid).

If no decoding exists, return 0.

Example 1

Input: s = "12"
Output: 2
Explanation: "AB" (1,2) or "L" (12).

Example 2

Input: s = "226"
Output: 3
Explanation: "BZ", "VF", or "BBF".

Example 3

Input: s = "06"
Output: 0
Explanation: "06" cannot map to any code.

Constraints

• 1 <= s.length <= 20
• s contains only digits.

Hints for Decode Ways

1. Hint 1

   dp over positions: ways(i) = ways(i-1) if s[i] != '0', plus ways(i-2) if s[i-1..i] is 10–26.

2. Hint 2

   A '0' must pair with a preceding 1 or 2, otherwise the count collapses to 0.

How to solve Decode Ways

A decoding is built by consuming the string from the left, one or two digits at a time. So the number of decodings of a prefix of length i is the count for i-1 (if the single digit s[i-1] is a valid code) plus the count for i-2 (if the pair s[i-2..i-1] is between 10 and 26). It is Fibonacci with validity conditions attached.

Approach

1. Return 0 immediately if the string starts with '0' — nothing can decode it.
2. Seed prev2 = 1 (empty prefix) and prev1 = 1 (first character, known valid).
3. For each i from 2 to |s|, start cur at zero.
4. If s[i-1] is not '0', add prev1 — the digit stands alone.
5. If the two-digit value s[i-2..i-1] lies in 10..26, add prev2. Shift the window and continue; prev1 ends as the answer.

Why it works

Every decoding has a unique final code, of length one or two, and stripping it leaves a decoding of a strictly shorter prefix. The two cases are disjoint (they consume different numbers of characters) and exhaustive, so adding their counts is exact. The validity guards are what make it more than Fibonacci: a '0' cannot stand alone, and a pair only counts if it names a real letter, which is why the leading digit of the pair must not be '0' either.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• "06" is invalid — a two-digit code must not have a leading zero, so the range check must start at 10, not 0.
• A '0' can never be decoded alone; it only survives as the second digit of 10 or 20.
• A string starting with '0' answers 0, and so does any string containing an undecodable zero — which falls out because cur becomes 0 and propagates.
• Seed prev2 = 1 for the empty prefix, or every two-digit code is undercounted.

Reference solution

Python

def numDecodings(s: str) -> int:
    if not s or s[0] == "0":
        return 0
    prev, cur = 1, 1
    for i in range(1, len(s)):
        nxt = 0
        if s[i] != "0":
            nxt += cur
        two = int(s[i - 1:i + 1])
        if 10 <= two <= 26:
            nxt += prev
        prev, cur = cur, nxt
        if cur == 0:
            return 0
    return cur

Java

public static int numDecodings(String s) {
    int n = s.length();
    if (s.charAt(0) == '0') return 0;
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = 0;
        if (s.charAt(i - 1) != '0') cur += prev1;
        int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
        if (two >= 10 && two <= 26) cur += prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

C++

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

JavaScript

var numDecodings = function(s) {
    if (s.length === 0 || s[0] === "0") return 0;
    let prev = 1, cur = 1;
    for (let i = 1; i < s.length; i++) {
        let next = 0;
        if (s[i] !== "0") next += cur;
        const two = parseInt(s.slice(i - 1, i + 1), 10);
        if (two >= 10 && two <= 26) next += prev;
        prev = cur;
        cur = next;
        if (cur === 0) return 0;
    }
    return cur;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium