Skip to main content
Talentd

Decode Ways II - Solution & Explanation

HardStringDynamic Programming13 min readAsked at: Amazon, Meta, PhonePe
Practice this problem

Problem Statement

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 109 + 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 <= 105
  • 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.

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.

Code

PythonJava

Python

Java

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.

This C solution optimizes space by maintaining only two integer variables, prev and curr, to store results of the previous and current positions respectively. This replaces the need for an entire dp array, reducing space usage while maintaining the dynamic programming logic.

Code

CJavaScript

C

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), as we use only constant extra space.

Try this approach in the editor β†’

Approach 3: Default Approach

Code

PythonJavaGo

Python

Java

Go

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
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 we use only constant extra space.

Default Approachβ€”

Detailed Complexity Analysis

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

Video Solution

θŠ±θŠ±ι…± LeetCode 639. Decode Ways II - εˆ·ι’˜ζ‰Ύε·₯作 EP110 β€’ Hua Hua β€’ 4,012 views views

Watch 9 more video solutions β†’

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.

Ready to solve this problem?

Practice Decode Ways II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Decode Ways

Next

Number of Ways to Divide a Long Corridor