437. Decode Ways II
A message of lowercase letters was encoded by replacing each letter with its alphabet position — 'a' → "1", 'b' → "2", …, 'z' → "26" — and concatenating the results. Decoding reverses this: split the digit string into chunks that are each a valid code "1" through "26" (a chunk may not start with '0') and map every chunk back to a letter.
The string you receive has an extra wrinkle: some characters were smudged and appear as '*'. A '*' stands for exactly one unknown digit from '1' to '9' — never '0'. Two decodings are different if they differ in any chosen digit or in how the string is split.
Your function receives the string s of digits and '*' characters and returns one integer: the total number of possible decodings, modulo 1,000,000,007. A string with no valid decoding yields 0.
Example 1:
Input: s = "*"
Output: 9
Explanation: The smudge is any digit 1–9, giving the nine one-letter messages "a" through "i".
Example 2:
Input: s = "1*"
Output: 18
Explanation: Split as two codes, '1' + '*' gives 9 decodings; read as one code, "1*" covers "11"–"19", another 9. Total 18.
Example 3:
Input: s = "2*"
Output: 15
Explanation: As two codes: 9 ways. As one code, "2*" can only be "21"–"26" (6 ways) since codes stop at 26. Total 15.
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s[i] is one of the characters 0-9 or *
- Return the count modulo 10⁹ + 7.
Hints:
Ignore the stars for a second. Plain Decode Ways is a Fibonacci-style DP: the number of decodings of the first i characters is dp[i] = dp[i−1] × (ways to read s[i−1] alone) + dp[i−2] × (ways to read s[i−2..i−1] as one two-digit code). Stars only change those two multipliers.
Work out the multiplier tables. Alone: '*' → 9, '0' → 0, any other digit → 1. As a pair: '1x' → 1 (or 9 if x is '*'), '2x' → 1 when x ≤ '6' (6 if x is '*'), '*x' → 2 when x ≤ '6', 1 when x > '6', and '**' → 15 (nine 1x codes plus six 2x codes). Take the result modulo 10^9 + 7 as you go, and keep only the last two dp values.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "*"
Expected output: 9