Decode Ways

Description

You have intercepted a secret message encoded as a string of digits. The message is decoded using the following mapping:

"1" → 'A', "2" → 'B', ..., "25" → 'Y', "26" → 'Z'

However, while decoding the message, you realize there are many different ways to decode it because some codes are contained within other codes (e.g., "2" and "5" vs "25").

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

Important notes:

A digit "0" cannot be decoded on its own — it must be part of a two-digit code ("10" or "20").
Leading zeros in a two-digit group are invalid (e.g., "06" is NOT valid, only "6" is).
The test cases are generated so that the answer fits in a 32-bit integer.

Examples

Example 1

Input: s = "12"

Output: 2

Explanation: "12" can be decoded as:

"AB" by grouping (1, 2) → A, B
"L" by grouping (12) → L

So there are 2 valid decodings.

Example 2

Input: s = "226"

Output: 3

Explanation: "226" can be decoded as:

"BZ" by grouping (2, 26) → B, Z
"VF" by grouping (22, 6) → V, F
"BBF" by grouping (2, 2, 6) → B, B, F

So there are 3 valid decodings.

Example 3

Input: s = "06"

Output: 0

Explanation: "06" cannot be mapped to "F" because of the leading zero. "6" is different from "06". The grouping (0, 6) is also invalid because "0" has no letter mapping. There is no valid way to decode this string, so the answer is 0.

Constraints

1 ≤ s.length ≤ 100
s contains only digits and may contain leading zero(s)

Editorial

Brute Force

Intuition

At every position in the string, you have a choice:

Take the current digit as a single-digit code (if it is not '0'), and recursively count the number of ways to decode the rest of the string starting from the next index.
Take the current digit and the next digit together as a two-digit code (if they form a number between 10 and 26), and recursively count the number of ways to decode the rest starting two positions ahead.

The total number of decodings from the current position is the sum of the decodings from both choices.

This is essentially a decision tree. At each position, you branch into one or two paths. The base case is when you reach the end of the string — that means you have found one valid decoding, so you return 1.

Think of it like reading a sentence where some words overlap. At each point, you can read one letter or two letters, and you want to count how many different readings are possible. You try every possibility by exploring all branches.

The problem with this approach is that it recomputes the same subproblems over and over. For example, decode(i+1) might be computed from multiple different positions, leading to exponential time.

Step-by-Step Explanation

Let's trace with s = "226":

Step 1: Start at index 0. s[0]='2' ≠ '0', so we can take it as a single digit.

Branch A: Decode '2' as 'B', recurse on "26" (index 1)
s[0..1]="22", 22 ≤ 26, so we can also take two digits.
Branch B: Decode '22' as 'V', recurse on "6" (index 2)

Step 2 (Branch A): At index 1, s[1]='2' ≠ '0'.

Branch A1: Decode '2' as 'B', recurse on "6" (index 2)
s[1..2]="26", 26 ≤ 26, valid two-digit.
Branch A2: Decode '26' as 'Z', recurse on "" (index 3)

Step 3 (Branch A1): At index 2, s[2]='6' ≠ '0'.

Decode '6' as 'F', recurse on "" (index 3)
Index 3 == length → base case, return 1.
No two-digit option (would go past end).
Result: 1 → This gives decoding "B" + "B" + "F" = "BBF"

Step 4 (Branch A2): Index 3 == length → return 1.

This gives decoding "B" + "Z" = "BZ"

Step 5 (Branch A total): 1 + 1 = 2

Step 6 (Branch B): At index 2, s[2]='6' ≠ '0'.

Decode '6' as 'F', recurse on "" (index 3) → return 1.
This gives decoding "V" + "F" = "VF"

Step 7 (Branch B total): 1

Step 8 (Final): Branch A (2) + Branch B (1) = 3

Recursion Tree — Decode Ways for "226" — Watch the recursion tree expand as we explore all possible decodings. Each node represents a recursive call with the remaining string. Leaf nodes at the end of the string each count as 1 valid decoding.

Algorithm

Define a recursive function decode(s, index)
Base case: If index >= s.length, return 1 (one valid decoding found)
Invalid case: If s[index] == '0', return 0 (a '0' cannot be decoded alone)
Single digit: Count ways = decode(s, index + 1)
Two digits: If index + 1 < s.length and the two-digit number s[index..index+1] is between 10 and 26, add decode(s, index + 2) to ways
Return ways
Call decode(s, 0) as the answer

Code

class Solution {
public:
    int numDecodings(string s) {
        return decode(s, 0);
    }
    
private:
    int decode(string& s, int index) {
        if (index >= (int)s.size()) return 1;
        if (s[index] == '0') return 0;
        
        int ways = decode(s, index + 1);
        
        if (index + 1 < (int)s.size()) {
            int twoDigit = (s[index] - '0') * 10 + (s[index + 1] - '0');
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += decode(s, index + 2);
            }
        }
        
        return ways;
    }
};

class Solution:
    def numDecodings(self, s: str) -> int:
        def decode(index: int) -> int:
            if index >= len(s):
                return 1
            if s[index] == '0':
                return 0
            
            ways = decode(index + 1)
            
            if index + 1 < len(s):
                two_digit = int(s[index:index + 2])
                if 10 <= two_digit <= 26:
                    ways += decode(index + 2)
            
            return ways
        
        return decode(0)

class Solution {
    public int numDecodings(String s) {
        return decode(s, 0);
    }
    
    private int decode(String s, int index) {
        if (index >= s.length()) return 1;
        if (s.charAt(index) == '0') return 0;
        
        int ways = decode(s, index + 1);
        
        if (index + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(index, index + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += decode(s, index + 2);
            }
        }
        
        return ways;
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each index, we make up to 2 recursive calls (one for single digit, one for two digits). This creates a binary recursion tree of depth n. In the worst case (e.g., a string of all '1's like "1111..."), every position branches twice, leading to 2^n total calls.

Space Complexity: O(n)

The recursion stack can go at most n levels deep (one level per character in the string). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force recursion is extremely slow because it recomputes the same subproblems repeatedly. For example, when computing decode(0), we call decode(1) and decode(2). But when computing decode(1), we also call decode(2). So decode(2) is computed twice. As the string gets longer, this overlap grows exponentially.

Consider the string "111111111" (nine 1's). decode(7) is computed from decode(5), decode(6), and potentially many other paths — each re-evaluating the same suffix independently. The total number of calls grows as O(2^n), making it impractical for strings of length 100.

This is a classic case of overlapping subproblems — the hallmark of a problem that can be optimized with dynamic programming. The key observation is:

decode(i) depends only on decode(i+1) and decode(i+2).
Once we compute decode(i), the result never changes.

By storing (memoizing) the result of each decode(i), we can avoid redundant computation entirely, reducing the time from exponential to linear.

Better Approach - Recursion with Memoization (Top-Down DP)

Intuition

The recursive structure is perfect — the only problem is redundant computation. The fix is simple: cache the result of each decode(i) so we never compute it twice.

We use a memoization array (or hash map) where memo[i] stores the number of decodings for the substring starting at index i. Before computing decode(i), we check if memo[i] already has a value. If it does, we return it immediately. If not, we compute it, store it, and return it.

This transforms the recursion tree into a directed acyclic graph (DAG) — each unique subproblem is solved exactly once, and its result is reused by any parent that needs it.

The recursion still works top-down (from index 0 toward the end), but with memoization, we ensure each index is processed only once, giving us O(n) time.

Step-by-Step Explanation

Let's trace with s = "226", using memo array initialized to -1:

Step 1: Call decode(0). memo[0] == -1, not cached. s[0]='2' ≠ '0'.

Single: call decode(1)
Two-digit: "22" ≤ 26 → call decode(2)

Step 2: Call decode(1). memo[1] == -1. s[1]='2' ≠ '0'.

Single: call decode(2)
Two-digit: "26" ≤ 26 → call decode(3)

Step 3: Call decode(2). memo[2] == -1. s[2]='6' ≠ '0'.

Single: call decode(3). Index 3 ≥ length → return 1.
No valid two-digit (past end).
memo[2] = 1. Return 1.

Step 4: Call decode(3). Index 3 ≥ length → return 1.

Step 5: Back in decode(1): single = decode(2) = 1 (from cache!), two-digit = decode(3) = 1.

memo[1] = 1 + 1 = 2. Return 2.

Step 6: Back in decode(0): single = decode(1) = 2, two-digit = decode(2) = 1 (from cache!).

memo[0] = 2 + 1 = 3. Return 3.

Notice: decode(2) was called from both decode(1) and decode(0), but only computed once — the second call was a cache hit.

Memoization Table — Building Up Results for "226" — Watch how each subproblem decode(i) is computed once and cached. Subsequent lookups return the stored value instantly, eliminating redundant work.

Algorithm

Create a memoization array memo of size n+1, initialized to -1
Define decode(index):
- If index >= n, return 1
- If s[index] == '0', return 0
- If memo[index] != -1, return memo[index] (cached result)
- Compute ways = decode(index + 1) (single digit)
- If two-digit s[index..index+1] is between 10 and 26, add decode(index + 2)
- Store memo[index] = ways
- Return ways
Return decode(0)

Code

class Solution {
public:
    int numDecodings(string s) {
        vector<int> memo(s.size(), -1);
        return decode(s, 0, memo);
    }
    
private:
    int decode(string& s, int index, vector<int>& memo) {
        if (index >= (int)s.size()) return 1;
        if (s[index] == '0') return 0;
        if (memo[index] != -1) return memo[index];
        
        int ways = decode(s, index + 1, memo);
        
        if (index + 1 < (int)s.size()) {
            int twoDigit = (s[index] - '0') * 10 + (s[index + 1] - '0');
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += decode(s, index + 2, memo);
            }
        }
        
        return memo[index] = ways;
    }
};

class Solution:
    def numDecodings(self, s: str) -> int:
        memo = {}
        
        def decode(index: int) -> int:
            if index >= len(s):
                return 1
            if s[index] == '0':
                return 0
            if index in memo:
                return memo[index]
            
            ways = decode(index + 1)
            
            if index + 1 < len(s):
                two_digit = int(s[index:index + 2])
                if 10 <= two_digit <= 26:
                    ways += decode(index + 2)
            
            memo[index] = ways
            return ways
        
        return decode(0)

class Solution {
    public int numDecodings(String s) {
        int[] memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return decode(s, 0, memo);
    }
    
    private int decode(String s, int index, int[] memo) {
        if (index >= s.length()) return 1;
        if (s.charAt(index) == '0') return 0;
        if (memo[index] != -1) return memo[index];
        
        int ways = decode(s, index + 1, memo);
        
        if (index + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(index, index + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += decode(s, index + 2, memo);
            }
        }
        
        return memo[index] = ways;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each of the n subproblems (decode(0), decode(1), ..., decode(n-1)) is computed at most once. Each computation does O(1) work (checking characters and making two lookups). So the total time is O(n).

Space Complexity: O(n)

We use a memoization array of size n to store the results. Additionally, the recursion stack can go up to n levels deep in the worst case. So total space is O(n).

Why This Approach Is Not Efficient

The memoized solution runs in O(n) time, which is already optimal in terms of time complexity. However, it still has two sources of overhead:

Recursion stack overhead: The top-down recursion uses O(n) call stack space. For very long strings (up to length 100), this is fine, but the recursive function call overhead (pushing/popping stack frames) is slower than a simple loop.
Extra space for full memo array: We store results for every index 0 to n-1. But notice the recurrence: decode(i) = decode(i+1) + decode(i+2). Each result depends only on the next two results, not on the entire array.

This suggests two improvements:

Bottom-up tabulation: Replace recursion with an iterative loop, eliminating stack overhead.
Space optimization: Since dp[i] depends only on dp[i+1] and dp[i+2], we only need two variables instead of an entire array — reducing space from O(n) to O(1).

Optimal Approach - Space-Optimized Bottom-Up DP

Intuition

Instead of solving top-down with recursion, we solve bottom-up with a simple loop — and instead of an array, we use just two variables.

The key recurrence is:
$dp[i] = dp[i+1] \times \mathbb{1}[\text{s[i]} \neq \text{'0'}] + dp[i+2] \times \mathbb{1}[10 \leq \text{s[i..i+1]} \leq 26]$

Since dp[i] only depends on dp[i+1] and dp[i+2], we can use two variables — let's call them next1 (representing dp[i+1]) and next2 (representing dp[i+2]) — and iterate from right to left.

Think of it like climbing a staircase from the end of the string backward. At each step, you look at the one step ahead and two steps ahead to decide how many paths lead from here to the end. You only ever need to remember the two steps immediately ahead of you.

The base case is: standing at the end of the string (past all characters), there is exactly 1 way to decode — the empty decoding. So next1 = 1 initially.

This approach is:

Iterative: No recursion, no stack overhead.
O(1) space: Just two variables instead of an array.
O(n) time: One pass through the string.

Step-by-Step Explanation

Let's trace with s = "226":

Step 1: Initialize: next1 = 1 (dp[3], past end), next2 = 0 (dp[4], out of range).

Step 2: i = 2, s[2] = '6' ≠ '0'.

Single digit valid: current = next1 = 1
Two digits: no index 3 exists → skip.
current = 1. Update: next2 = next1 = 1, next1 = current = 1.

Step 3: i = 1, s[1] = '2' ≠ '0'.

Single digit valid: current = next1 = 1
Two digits: s[1..2] = "26", 26 ≤ 26 → valid: current += next2 = 1. current = 2.
Update: next2 = next1 = 1, next1 = current = 2.

Step 4: i = 0, s[0] = '2' ≠ '0'.

Single digit valid: current = next1 = 2
Two digits: s[0..1] = "22", 22 ≤ 26 → valid: current += next2 = 1. current = 3.
Update: next2 = next1 = 2, next1 = current = 3.

Step 5: Loop finished. Answer = next1 = 3.

We computed the same answer as before but using only O(1) extra space and no recursion.

Space-Optimized DP — Two Variables Sliding Right-to-Left — Watch how two variables (next1 and next2) slide from right to left across the string, building up the count of decodings without needing a full array.

Algorithm

If the string is empty or starts with '0', return 0
Initialize next1 = 1 (represents dp[n], base case) and next2 = 0 (represents dp[n+1])
Iterate from i = n-1 down to 0:
- Set current = 0
- If s[i] != '0': add next1 to current (single-digit decoding)
- If i + 1 < n and s[i..i+1] forms a number between 10 and 26: add next2 to current (two-digit decoding)
- Shift: next2 = next1, next1 = current
Return next1 (which now holds dp[0])

Code

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if (n == 0 || s[0] == '0') return 0;
        
        int next1 = 1;  // dp[n]
        int next2 = 0;  // dp[n+1]
        
        for (int i = n - 1; i >= 0; i--) {
            int current = 0;
            
            if (s[i] != '0') {
                current = next1;
            }
            
            if (i + 1 < n) {
                int twoDigit = (s[i] - '0') * 10 + (s[i + 1] - '0');
                if (twoDigit >= 10 && twoDigit <= 26) {
                    current += next2;
                }
            }
            
            next2 = next1;
            next1 = current;
        }
        
        return next1;
    }
};

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0
        
        next1 = 1  # dp[n]
        next2 = 0  # dp[n+1]
        
        for i in range(n - 1, -1, -1):
            current = 0
            
            if s[i] != '0':
                current = next1
            
            if i + 1 < n:
                two_digit = int(s[i:i + 2])
                if 10 <= two_digit <= 26:
                    current += next2
            
            next2 = next1
            next1 = current
        
        return next1

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') return 0;
        
        int next1 = 1;  // dp[n]
        int next2 = 0;  // dp[n+1]
        
        for (int i = n - 1; i >= 0; i--) {
            int current = 0;
            
            if (s.charAt(i) != '0') {
                current = next1;
            }
            
            if (i + 1 < n) {
                int twoDigit = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
                if (twoDigit >= 10 && twoDigit <= 26) {
                    current += next2;
                }
            }
            
            next2 = next1;
            next1 = current;
        }
        
        return next1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the string exactly once from right to left. Each iteration does O(1) work — checking characters, computing a two-digit number, and updating two variables. Total: O(n).

Space Complexity: O(1)

We use only two integer variables (next1 and next2) regardless of the input size. No arrays, no recursion stack. This is the most space-efficient solution possible.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Decode Ways

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Recursion with Memoization (Top-Down DP)

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Space-Optimized Bottom-Up DP

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis