639. Decode Ways II - Solution

The 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.

Example 1:

Input: s = "*"
Output: 9
Explanation: The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9".
Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively.
Hence, there are a total of 9 ways to decode "*".

Example 2:

Input: s = "1*"
Output: 18
Explanation: The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19".
Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K").
Hence, there are a total of 9 * 2 = 18 ways to decode "1*".

Example 3:

Input: s = "2*"
Output: 15
Explanation: The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29".
"21", "22", "23", "24", "25", and "26" have 2 ways of being decoded, but "27", "28", and "29" only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode "2*".

Constraints:

1 <= s.length <= 10⁵
s[i] is a digit or '*'.

Approach overview

Problem Overview: You receive a string of digits representing encoded letters where '1' -> 'A' through '26' -> 'Z'. The twist is the character *, which can represent any digit from 1 to 9. Your task is to count how many valid decoding ways exist for the entire string. The answer can grow large, so return it modulo 1e9 + 7. This problem combines tricky case handling with classic dynamic programming over a string.

Approach 1: Dynamic Programming (O(n) time, O(n) space)

Use a DP array where dp[i] represents the number of ways to decode the prefix ending at index i. At each position, evaluate two possibilities: decoding the current character alone, and decoding the current character together with the previous one. Handling * is the key challenge because it expands into multiple valid digits. For example, a single * contributes 9 possibilities, while combinations like 1* produce 9 valid pairs and 2* produce 6. Similarly, ** creates 15 valid two-digit combinations (11–19 and 21–26). Iterate through the string, update dp[i] using these rules, and apply modulo arithmetic to prevent overflow. This approach is straightforward to reason about because every state explicitly stores the number of ways up to that index.

Approach 2: Space Optimized Dynamic Programming (O(n) time, O(1) space)

The recurrence only depends on the previous two states, so you can eliminate the full DP array. Maintain two variables: one for the number of ways to decode up to the previous position and one for the position before that. As you scan the string from left to right, compute the current number of ways using the same transition logic as the DP solution: single-character decoding and two-character decoding. Carefully handle cases involving *, such as *0, *7, or **, by counting the valid digit combinations that map to numbers between 10 and 26. After computing the new value, shift the variables forward. This keeps memory constant while preserving the same logic and correctness.

Both approaches rely on recognizing valid one-digit and two-digit decoding patterns while expanding wildcard possibilities. The core observation is that every index contributes ways derived from the previous one or two indices. The DP transition encodes all legal combinations defined by the mapping rules.

Recommended for interviews: Interviewers typically expect the space-optimized dynamic programming approach. It demonstrates that you understand the recurrence and can reduce memory usage from O(n) to O(1). Starting with the full DP table is a good way to explain your thinking. Then compress the state to show deeper mastery of dynamic programming patterns on string decoding problems.

Approach 1: Dynamic Programming

This approach utilizes a dynamic programming (DP) technique to solve the problem. We define a DP array where dp[i] represents the number of ways to decode the substring of length i. We iterate through the string, updating the DP array based on the current character and its possible pairings with the previous character.

Python

def numDecodings(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    if n == 0:
        return 0
    
    dp = [0] * (n + 1)
    dp[0] = 1
    
    if s[0] == '*':
        dp[1] = 9
    elif s[0] != '0':
        dp[1] = 1
    
    for i in range(2, n + 1):
        
        first = s[i-1]
        second = s[i-2]

        if first == '*':
            dp[i] = 9 * dp[i-1]
        elif first != '0':
            dp[i] = dp[i-1]

        if second == '*':
            if first == '*':
                dp[i] = (dp[i] + 15 * dp[i-2]) % MOD
            elif '0' <= first <= '6':
                dp[i] = (dp[i] + 2 * dp[i-2]) % MOD
            else:
                dp[i] = (dp[i] + dp[i-2]) % MOD
        elif second == '1':
            if first == '*':
                dp[i] = (dp[i] + 9 * dp[i-2]) % MOD
            else:
                dp[i] = (dp[i] + dp[i-2]) % MOD
        elif second == '2':
            if first == '*':
                dp[i] = (dp[i] + 6 * dp[i-2]) % MOD
            elif '0' <= first <= '6':
                dp[i] = (dp[i] + dp[i-2]) % MOD
    
    return dp[n] % MOD

Java

public class Solution {
    public int numDecodings(String s) {
        int MOD = 1000000007;
        int n = s.length();
        if (n == 0) return 0;

        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '*' ? 9 : s.charAt(0) != '0' ? 1 : 0;

        for (int i = 2; i <= n; i++) {
            char first = s.charAt(i - 1);
            char second = s.charAt(i - 2);

            if (first == '*') {
                dp[i] += 9 * dp[i - 1];
            } else if (first != '0') {
                dp[i] += dp[i - 1];
            }

            if (second == '*') {
                if (first == '*') {
                    dp[i] += 15 * dp[i - 2];
                } else if (first <= '6') {
                    dp[i] += 2 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (second == '1') {
                if (first == '*') {
                    dp[i] += 9 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (second == '2') {
                if (first == '*') {
                    dp[i] += 6 * dp[i - 2];
                } else if (first <= '6') {
                    dp[i] += dp[i - 2];
                }
            }

            dp[i] %= MOD;
        }

        return (int) dp[n];
    }
}

This solution introduces a dynamic programming approach. The dp[i] array stores the number of decoding ways for the substring up to the ith character. The initial state is set based on the first character, considering '.' as all digits 1-9. Each subsequent character adjusts dp[i] depending on its value and the preceding character(s), also accounting for the '*' possibilities. All computations are done modulo 10^9 + 7 to limit overflow.

Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(n), due to the dynamic programming array used.

Try this approach in the editor

Approach 2: Space Optimized Dynamic Programming

This is a space-optimized version of the dynamic programming solution. Instead of using a full dp array, we keep track of only the last two states needed, thereby reducing space complexity.

JavaScript

function numDecodings(s) {
    const MOD = 1000000007;
    let n = s.length;

    if (n === 0) return 0;

    let prev = 1, curr = s[0] === '*' ? 9 : s[0] !== '0' ? 1 : 0;

    for (let i = 1; i < n; i++) {
        let temp = curr;
        let first = s[i];
        let second = s[i - 1];

        curr = 0;

        if (first === '*') {
            curr = 9 * temp;
        } else if (first !== '0') {
            curr = temp;
        }

        if (second === '*') {
            if (first === '*') {
                curr = (curr + 15 * prev) % MOD;
            } else if (first <= '6') {
                curr = (curr + 2 * prev) % MOD;
            } else {
                curr = (curr + prev) % MOD;
            }
        } else if (second === '1') {
            if (first === '*') {
                curr = (curr + 9 * prev) % MOD;
            } else {
                curr = (curr + prev) % MOD;
            }
        } else if (second === '2') {
            if (first === '*') {
                curr = (curr + 6 * prev) % MOD;
            } else if (first <= '6') {
                curr = (curr + prev) % MOD;
            }
        }

        prev = temp;
    }

    return curr;
}

#include <string.h>

#define MOD 1000000007

int numDecodings(char* s) {
    int n = strlen(s);
    if (n == 0) return 0;

    long prev = 1, curr = s[0] == '*' ? 9 : s[0] != '0' ? 1 : 0;

    for (int i = 1; i < n; i++) {
        long temp = curr;
        char first = s[i];
        char second = s[i - 1];

        curr = 0;

        if (first == '*') {
            curr = 9 * temp;
        } else if (first != '0') {
            curr = temp;
        }

        if (second == '*') {
            if (first == '*') {
                curr = (curr + 15 * prev) % MOD;
            } else if (first <= '6') {
                curr = (curr + 2 * prev) % MOD;
            } else {
                curr = (curr + prev) % MOD;
            }
        } else if (second == '1') {
            if (first == '*') {
                curr = (curr + 9 * prev) % MOD;
            } else {
                curr = (curr + prev) % MOD;
            }
        } else if (second == '2') {
            if (first == '*') {
                curr = (curr + 6 * prev) % MOD;
            } else if (first <= '6') {
                curr = (curr + prev) % MOD;
            }
        }

        prev = temp;
    }

    return (int)curr;
}

This JavaScript solution is similarly optimized in terms of space, using only two variables to track the last two relevant decoding states. It follows dynamic programming principles while using inline conditions to handle single characters and pairs efficiently.

Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), as only fixed space is used for computation.

Try this approach in the editor

Approach 3: Default Approach

const mod int = 1e9 + 7

func numDecodings(s string) int {
	n := len(s)

	// dp[i - 2], dp[i - 1], dp[i]
	a, b, c := 0, 1, 0
	for i := 1; i <= n; i++ {
		// 1 digit
		if s[i-1] == '*' {
			c = 9 * b % mod
		} else if s[i-1] != '0' {
			c = b
		} else {
			c = 0
		}

		// 2 digits
		if i > 1 {
			if s[i-2] == '*' && s[i-1] == '*' {
				c = (c + 15*a) % mod
			} else if s[i-2] == '*' {
				if s[i-1] > '6' {
					c = (c + a) % mod
				} else {
					c = (c + 2*a) % mod
				}
			} else if s[i-1] == '*' {
				if s[i-2] == '1' {
					c = (c + 9*a) % mod
				} else if s[i-2] == '2' {
					c = (c + 6*a) % mod
				}
			} else if s[i-2] != '0' && (s[i-2]-'0')*10+s[i-1]-'0' <= 26 {
				c = (c + a) % mod
			}
		}

		a, b = b, c
	}
	return c
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming	Time Complexity: O(n), where `n` is the length of the input string. Space Complexity: O(n), due to the dynamic programming array used.
Space Optimized Dynamic Programming	Time Complexity: O(n), where `n` is the length of the input string. Space Complexity: O(1), as only fixed space is used for computation.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming	O(n)	O(n)	Best for understanding transitions clearly and debugging wildcard decoding rules
Space Optimized Dynamic Programming	O(n)	O(1)	Preferred in interviews or memory-constrained environments since only two previous states are required

Frequently asked questions

Is Decode Ways II easy or hard?

Decode Ways II is classified as Hard because handling the '*' wildcard introduces many edge cases. Candidates must correctly count multiple digit possibilities and integrate them into a dynamic programming recurrence without double counting.

Decode Ways II Python/Java solution

Python and Java solutions typically implement the dynamic programming recurrence with modulo arithmetic. The algorithm iterates through the string, counts valid combinations for characters and pairs involving '*', and updates the DP states in O(n) time.

How to solve Decode Ways II in O(n)?

Iterate through the string and maintain two DP states representing decoding counts for the previous and second previous indices. At each step compute contributions from single-character decoding and two-character decoding. Handle '*' by counting all valid digit combinations, and apply modulo 1e9+7 after each update.

What is the best approach for Decode Ways II?

The best approach is dynamic programming with constant space optimization. Track the number of decoding ways using the previous two states while iterating through the string. This method handles wildcard '*' combinations efficiently and runs in O(n) time with O(1) space.

Is Decode Ways II asked at Google/Amazon/Meta?

Decode Ways style problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test dynamic programming, string processing, and careful case analysis. The wildcard extension in Decode Ways II makes it a harder follow-up variant.

What data structure is used in Decode Ways II?

The primary technique uses dynamic programming over a string. A DP array or two rolling variables store the number of ways to decode prefixes of the string while checking valid one-digit and two-digit mappings between 1 and 26.

What is the time complexity of Decode Ways II?

Decode Ways II can be solved in O(n) time where n is the length of the string. Each character is processed once, and only constant-time calculations are performed to account for single-digit and two-digit decoding possibilities including '*' cases.

Decode Ways II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming

Approach 2: Space Optimized Dynamic Programming

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Decode Ways II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming

Approach 2: Space Optimized Dynamic Programming

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems