Decode Ways II - Practice Coding Problems

Decode Ways II - Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways).

For example, "11106" can be mapped into:

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

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

In addition to the mapping above, an encoded message may contain the '*' character, which can represent any digit from '1' to '9' ('0' is excluded). For example, the encoded message "1*" may represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19". Decoding "1*" is equivalent to decoding any of the encoded messages it can represent.

Given a string s consisting of digits and '*' characters, return the number of ways to decode it. Since the answer may be very large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Wildcard

$ Input: s = "*"

› Output: 9

💡 Note: The * can be any digit 1-9, each giving one valid decode way: 'A' through 'I'

Example 2 — Two Digit Combinations

$ Input: s = "1*"

› Output: 18

💡 Note: Can decode as: single digits '1' + '*' (1×9=9 ways), or two digits '1*' as 11-19 (9 ways). Total: 9+9=18

Example 3 — Complex Pattern

$ Input: s = "2*"

› Output: 15

💡 Note: Single digits: '2' + '*' (1×9=9 ways). Two digits: '2*' as 21-26 (6 ways). Total: 9+6=15

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is a digit or '*'
Answer modulo 10⁹ + 7

Visualization

Tap to expand

Understanding the Visualization

Input

String with digits and * wildcards

Process

Count all valid decode combinations

Output

Total number of ways modulo 10⁹+7

Key Takeaway

🎯 Key Insight: Wildcards multiply the number of valid decodings, requiring careful counting of all possibilities

Asked in

G Google 45 f Facebook 38 a Amazon 32

The key insight is that wildcards multiply possibilities - each * can be 1-9 for single digits, and specific ranges for two digits. Best approach uses dynamic programming to count decode ways efficiently. Time: O(n), Space: O(1) with optimization.

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n)	O(n)	Build solution from base cases using 1D DP array
Space-Optimized DP	O(n)	O(1)	Optimize space by using only three variables instead of full DP array
Recursive with Memoization	O(n)	O(n)	Recursively try all possible decodings with memoization

Bottom-Up Dynamic Programming — Algorithm Steps

Initialize dp array with base cases
For each position, calculate single and double digit contributions
Handle * wildcards by counting all valid digit substitutions
Return dp[0] as final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[n] = 1 as base case

Fill Array

Process each position from right to left

Result

dp[0] contains total decode ways

Code -

solution.c — C

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

#define MOD 1000000007
#define MAXN 100005

int solution(char* s) {
    int n = strlen(s);
    long long dp[MAXN];
    memset(dp, 0, sizeof(dp));
    dp[n] = 1;
    
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '0') {
            dp[i] = 0;
            continue;
        }
        
        // Single digit
        if (s[i] == '*') {
            dp[i] = (dp[i] + 9LL * dp[i + 1]) % MOD;
        } else {
            dp[i] = (dp[i] + dp[i + 1]) % MOD;
        }
        
        // Two digits
        if (i + 1 < n) {
            if (s[i] == '*') {
                if (s[i + 1] == '*') {
                    dp[i] = (dp[i] + 15LL * dp[i + 2]) % MOD;
                } else if (s[i + 1] <= '6') {
                    dp[i] = (dp[i] + 2LL * dp[i + 2]) % MOD;
                } else {
                    dp[i] = (dp[i] + dp[i + 2]) % MOD;
                }
            } else if (s[i] == '1') {
                if (s[i + 1] == '*') {
                    dp[i] = (dp[i] + 9LL * dp[i + 2]) % MOD;
                } else {
                    dp[i] = (dp[i] + dp[i + 2]) % MOD;
                }
            } else if (s[i] == '2') {
                if (s[i + 1] == '*') {
                    dp[i] = (dp[i] + 6LL * dp[i + 2]) % MOD;
                } else if (s[i + 1] <= '6') {
                    dp[i] = (dp[i] + dp[i + 2]) % MOD;
                }
            }
        }
    }
    
    return (int)dp[0];
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string, constant work per position

✓ Linear Growth

Space Complexity

O(n)

DP array stores result for each position

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

892 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

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler