Pager Readings With Smudges
Problem
Pager messages use the code A → 1, ..., Z → 26. Some digits of the received message s are smudged and shown as *. A smudge stands for any digit from 1 to 9 (never 0).
Count the total number of ways to read the message: every way of replacing the smudges, combined with every valid split into codes (1–9, or 10–26 with two digits; no piece starts with 0). Return the count modulo 10^9 + 7.
Example 1
- Input:
- s = "*"
- Output:
- 9
The smudge is one of 1–9, each read as a single letter.
Example 2
- Input:
- s = "1*"
- Output:
- 18
9 readings as two single digits, plus 9 readings as one code 11–19.
Example 3
- Input:
- s = "2*"
- Output:
- 15
9 single-digit readings, plus 6 codes 21–26.
Constraints
- 1 ≤ s.length ≤ 10^5
- s[i] is a digit 0–9 or '*'.
Hint
Show the first hint
Keep the plain decoding recurrence: ways[i] = (one-digit options) · ways[i-1] + (two-digit options) · ways[i-2].
Walkthrough
How to approach it
01Clarify before coding
- Can '*' be 0? No, only 1–9; so "*0" is 10 or 20 (2 readings).
- Do different replacements count separately even when they give the same letters? Each (replacement, split) pair counts once; different replacements are different messages.
- How long can s be? 10^5, so the solution must be linear.
02Brute force
Replace every '*' in all 9^k ways and run the ordinary decoding count on each result.
Cost: O(9^k · n) where k is the number of smudges: 9^1000 for an all-smudge message.
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.