Decode Ways - Practice Coding Problems

Decode Ways - Problem

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

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

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

"AAJF" with the grouping (1, 1, 10, 6)
"KJF" with the grouping (11, 10, 6)

The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: There may be strings that are impossible to decode.

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "12"

› Output: 2

💡 Note: Two ways to decode: "1"+"2" → AB, or "12" → L. Both are valid decodings.

Example 2 — Multiple Options

$ Input: s = "226"

› Output: 3

💡 Note: Three ways: "2"+"2"+"6" → BBF, "2"+"26" → BZ, "22"+"6" → VF. All valid decodings.

Example 3 — Leading Zero

$ Input: s = "06"

› Output: 0

💡 Note: Cannot decode because "06" is invalid (leading zero) and "0" alone is invalid. No valid decodings.

Constraints

1 ≤ s.length ≤ 100
s contains only digits
s may have leading zeros

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits like "226"

Process

Find all valid ways to split into 1-26 ranges

Output

Count of valid decodings

Key Takeaway

🎯 Key Insight: At each position, we can take 1 digit (1-9) or 2 digits (10-26), building solutions incrementally

Asked in

F Facebook 45 M Microsoft 38 G Google 32 a Amazon 28

The key insight is that each position depends on the previous 1-2 positions, making it a perfect dynamic programming problem. The optimal approach uses space-optimized DP with two variables. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n)	O(n)	Add memoization to avoid recalculating same subproblems
Recursive Brute Force	O(2ⁿ)	O(n)	Try all possible ways to split the string recursively
Dynamic Programming	O(n)	O(n)	Build solution bottom-up using 1D DP array
Space-Optimized DP	O(n)	O(1)	Optimize space by using only two variables instead of full array

Memoized Recursion — Algorithm Steps

Use recursion with memo table
Check memo before computing
Store result in memo after computing
Return memoized result

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute

Calculate result for each index once

Store

Save result in memo table

Reuse

Return cached result for repeated calls

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int memo[101];
static int memo_set[101];

int decode(char* s, int index, int len) {
    if (memo_set[index]) {
        return memo[index];
    }
    if (index == len) {
        return 1;
    }
    if (s[index] == '0') {
        memo[index] = 0;
        memo_set[index] = 1;
        return 0;
    }
    
    int ways = 0;
    // Take 1 digit
    ways += decode(s, index + 1, len);
    
    // Take 2 digits if valid
    if (index + 1 < len) {
        int twoDigit = (s[index] - '0') * 10 + (s[index + 1] - '0');
        if (twoDigit >= 10 && twoDigit <= 26) {
            ways += decode(s, index + 2, len);
        }
    }
    
    memo[index] = ways;
    memo_set[index] = 1;
    return ways;
}

int solution(char* s) {
    memset(memo_set, 0, sizeof(memo_set));
    return decode(s, 0, strlen(s));
}

int main() {
    char s[101];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each index computed once, stored in memo for O(1) future lookups

✓ Linear Growth

Space Complexity

O(n)

Memo table stores n results plus recursion stack depth

⚡ Linearithmic Space

89.3K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler