Wildcard Message Decodings
Problem
Letters are encoded as numbers (A → 1, …, Z → 26) and joined without separators. This time the scanned string s is partly smudged: each * stands for one unknown digit from 1 to 9 (never 0).
Return the total number of letter messages that could have produced s, over all ways of filling the *s, modulo 1,000,000,007. Codes never have leading zeros.
Example 1
- Input:
- s = "*"
- Output:
- 9
Any of A through I.
Example 2
- Input:
- s = "1*"
- Output:
- 18
Nine ways as two letters (1 then 1–9) and nine as one letter (11–19).
Example 3
- Input:
- s = "2*"
- Output:
- 15
Nine as two letters, and 21–26 as one letter: 9 + 6.
Constraints
- 1 ≤ s.length ≤ 10^5
- s contains digits and '*'.
Hint
Show the first hint
Keep the two-case recurrence from plain decoding: the last letter used one character or two.
Walkthrough
How to approach it
01Clarify before coding
- Can '*' be 0? No, only 1–9. That matters for '*0' (only 10 and 20) and for pairs like '**' (no 20).
- Are different fillings of the stars that give the same letters counted separately? Each (filling, split) pair yields a distinct message here, so yes, simply count them.
- How long can s be? 10^5, so the solution must be linear.
02Brute force
Expand every '*' into 9 digits and decode each concrete string with the plain DP.
Cost: O(9^m · n) for m stars: hopeless with even 20 stars.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.