Decode Ways II LeetCode 639 — DP Guide

LeetCode 639 Decode Ways II is a follow-up to LeetCode 91 Decode Ways. You are given an encoded string s consisting of digits '1'–'9', '0', and the special wildcard character '*'. The mapping is the same as before: a digit string can be decoded as A=1, B=2, ..., Z=26. The wildcard '*' can represent any single digit from '1' through '9' (it never represents '0'). Your task is to count the total number of ways to decode s and return the answer modulo 10^9+7.

The wildcard character makes the problem significantly harder than LeetCode 91. A single '*' expands to 9 possibilities for single-character decoding. When '*' appears in a two-character pair, you must enumerate which combinations form valid two-digit codes (10–26). This four-way case analysis — digit-digit, digit-star, star-digit, star-star — is the heart of the problem and where most bugs originate.

The answer must be returned modulo 10^9+7 because the number of decodings can be astronomically large. For a string of all '*' characters with length n, the count grows exponentially. The modulus prevents integer overflow, but you must apply it consistently at every arithmetic step, not just at the end.

LeetCode 91 Decode Ways defines dp[i] as the number of ways to decode the first i characters of s. The recurrence has two contributions: the single-digit decode (if s[i-1] is not '0', then dp[i] += dp[i-1]) and the two-digit decode (if s[i-2..i-1] forms a valid code 10–26, then dp[i] += dp[i-2]). The base cases are dp[0] = 1 (empty string has one way to decode) and dp[1] = 1 if s[0] != '0' else 0.

In LeetCode 639, the same structure applies — dp[i] still accumulates single-digit and two-digit contributions — but now s[i-1] or s[i-2] can be '*', which means each character can represent multiple digits simultaneously. Instead of a binary is-valid check, we multiply dp[i-1] by the number of valid single-digit interpretations (0, 1, or 9) and dp[i-2] by the number of valid two-digit interpretations (0 to 15). The modular arithmetic must be applied after each multiplication to keep values bounded.

Because dp[i] depends only on dp[i-1] and dp[i-2], we can replace the O(n) array with two rolling scalar variables — exactly as in the space-optimized version of LeetCode 91. This makes the solution O(n) time and O(1) space, which is the expected optimal complexity for this problem.

The single-digit contribution to dp[i] comes from looking at s[i-1] (the current character) alone. If s[i-1] is a digit '1'–'9', it contributes 1 valid interpretation, so dp[i] += 1 * dp[i-1]. If s[i-1] is '0', it contributes 0 valid interpretations ('0' cannot be decoded alone), so dp[i] += 0. If s[i-1] is '*', it can represent any digit '1'–'9' — exactly 9 options — so dp[i] += 9 * dp[i-1].

This three-way case analysis for the single-digit contribution is straightforward. The wildcard multiplier of 9 reflects the fact that '*' simultaneously represents all nine non-zero digits. When you reach s[i-1] = '*', you are not choosing one of the nine interpretations — you are counting all of them, so the number of paths is multiplied by 9 before being added into dp[i].

Be careful to apply the modulus after the multiplication: dp[i] = (dp[i] + 9 * dp[i-1]) % MOD. In Java and C++, where integer overflow is a real concern, multiplying dp[i-1] (which can be up to MOD-1 ≈ 10^9) by 9 can produce a value up to about 9 * 10^9, which overflows a 32-bit int but fits in a 64-bit long. Always use long (Java) or long long (C++) for intermediate products.

The two-digit contribution to dp[i] comes from looking at s[i-2..i-1] as a pair. Valid two-digit codes are 10–26. When neither character is '*', this is the same as LeetCode 91: check if the two-character string forms an integer in [10, 26]. When one or both characters are '*', you must count how many two-digit combinations the pair can form in [10, 26].

Case 1 — digit-digit (neither is '*'): parse the two characters as an integer t; if 10 ≤ t ≤ 26, add dp[i-2]. Case 2 — digit-star (s[i-2] is a digit d, s[i-1] is '*'): '*' can be '1'–'9', so the pair is d1, d2, ..., d9. Count how many of these fall in [10, 26]: if d=='1', all 9 work (11–19); if d=='2', digits '1'–'6' work (21–26), giving 6; otherwise 0. Case 3 — star-digit (s[i-2] is '*', s[i-1] is a digit d): '*' can be '1' or '2'; if '*'='1', the pair is 1d (valid if 10≤1d≤19, i.e., always for d in 0–9); if '*'='2', the pair is 2d (valid if 20≤2d≤26, i.e., d in 0–6). Count the valid options and multiply by dp[i-2].

Case 4 — star-star (both are '*'): the first '*' can be '1' or '2'; if '1', the second '*' can be '1'–'9' (9 options: 11–19); if '2', the second '*' can be '1'–'6' (6 options: 21–26). Total: 15 valid combinations. So the two-star contribution is 15 * dp[i-2].

The problem requires the answer modulo 10^9+7 (1000000007, a prime). For strings with many '*' characters, the count of decodings grows exponentially — a string of n '*' characters can produce on the order of 15^(n/2) decodings, which for n=10^5 is astronomically large. If you delay the modulus until the final return statement, every intermediate dp value will overflow long before then, producing garbage results.

The correct approach is to apply % MOD after every addition and multiplication. For additions: dp[i] = (dp[i] + contribution) % MOD. For multiplications: the contribution itself must be reduced: (count * prev) % MOD, where count is at most 15 and prev is at most MOD-1 ≈ 10^9. The product count * prev can be up to 15 * 10^9 ≈ 1.5 * 10^10, which fits in a 64-bit integer (max ~9.2 * 10^18) but not a 32-bit integer. Use long in Java, long long in C++, and Python's arbitrary precision handles it automatically.

A subtle issue: when you use rolling variables (prev2 = dp[i-2], prev1 = dp[i-1]) and update them each step, you must ensure the updated values are already reduced mod MOD before the next iteration uses them. If you forget to apply % MOD when updating the rolling variables, they grow unboundedly and corrupted values propagate forward through the entire DP.

Python O(n) time O(1) space: def numDecodings(s): MOD = 10**9+7; prev2, prev1 = 1, (9 if s[0]=='*' else (0 if s[0]=='0' else 1)); for i in range(1, len(s)): cur = 0; c, p = s[i], s[i-1]; single = 9 if c=='*' else (0 if c=='0' else 1); cur = single * prev1 % MOD; if p=='*' and c=='*': cur = (cur + 15*prev2) % MOD; elif p=='*': cur = (cur + (9 if c<='6' else 6 if c=='7' or c=='8' or c=='9' else 0) * prev2) % MOD # star-digit; elif c=='*': cur = (cur + (9 if p=='1' else 6 if p=='2' else 0) * prev2) % MOD # digit-star; else: t = int(p+c); cur = (cur + prev2) % MOD if 10<=t<=26 else cur; prev2, prev1 = prev1, cur; return prev1. The star-digit case: if p='*', count pairs *d in [10,26]; d can be any digit so *='1' gives 10–1d valid (all), *='2' gives valid only if d<=6.

Java O(n) time O(1) space: public int numDecodings(String s) { long MOD = 1_000_000_007L; char f = s.charAt(0); long prev2 = 1, prev1 = f=='*' ? 9 : f=='0' ? 0 : 1; for (int i=1; i<s.length(); i++) { char c=s.charAt(i), p=s.charAt(i-1); long cur=0; long single = c=='*' ? 9 : c=='0' ? 0 : 1; cur = single*prev1%MOD; if (p=='*'&&c=='*') cur=(cur+15*prev2)%MOD; else if (p=='*') cur=(cur+(c<='6'?9:6)*prev2)%MOD; // wait: p='*' means first digit is *, second is c (digit). *c valid: if *=1 → 1c always valid (10-19, 9 options); if *=2 → 2c valid iff c<=6 (6 options). So count = (c<='6'?9+6:9) → actually: count = 9 (for *=1) + (c<='6'?6:0) (for *=2); else if (c=='*') { int t=p-'0'; cur=(cur+(t==1?9:t==2?6:0)*prev2)%MOD; } else { int t=(p-'0')*10+(c-'0'); cur=(cur+(t>=10&&t<=26?prev2:0))%MOD; } prev2=prev1; prev1=cur; } return (int)prev1; } The star-digit pair (p='*', c=digit): first digit is '*' (can be 1 or 2). If '*'=1: pair is 1c, always in [10,19] → valid for any digit c, giving 9 ways. If '*'=2: pair is 2c, valid only if c in [0,6] → 6 ways if c<=6, else 0. Total = 9 + (c<='6'?6:0).

Both solutions run in O(n) time and O(1) space using two rolling scalars prev1 (dp[i-1]) and prev2 (dp[i-2]). The trickiest edge case is the star-digit pair where p='*': do not confuse "first digit is '*'" with "second digit is '*'". Draw out the four cases explicitly before coding and test with s="*" (9), s="**" (96: 9*9 single + 15 two-digit... wait: for "**": dp[1] = 9*dp[0] + 15*dp[-1]... base case handling), and s="*0" (2: '*'=2 gives "20", '*'=1–9 all give *0 which is invalid except no — '*0' as two-digit: first '*' must be 1 or 2 and second '0' means 10 or 20, both valid → 2 ways; as single: '0' alone is invalid → 0; total = 2).

Decode Ways (LeetCode 91) is the direct predecessor. Solving it builds the dp[i] = single-digit + two-digit recurrence intuition and the O(1) space rolling-variable pattern. Every technique in LeetCode 639 is an extension of LeetCode 91, so it is the essential prerequisite. If you find LeetCode 639 overwhelming, return to LeetCode 91, implement the O(1) space version with rolling variables, and then map each '*'-related case in 639 onto its corresponding non-wildcard case in 91.

Paint House (LeetCode 256) shares the same DP shape: dp[i] depends on dp[i-1], the state space is small (3 colors vs 2 decode options), and O(1) space is achievable with rolling variables. The key difference is that Paint House uses min instead of sum, but the structural analogy is strong. Working through Paint House helps solidify the "rolling variables updated simultaneously" technique that also applies to Decode Ways II.

Combination Sum IV (LeetCode 377) and Number of Ways to Decode problems more broadly test whether you can extend a counting DP to handle richer character classes. For harder extensions, look at LeetCode 940 Distinct Subsequences II and LeetCode 1269 Number of Ways to Stay in the Same Place After Some Steps — both require modular arithmetic and careful state expansion, the same two skills that define Decode Ways II.