Decode Ways II - Solution & Explanation

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.