hardDynamic Programming 1DAI-applied~35 min
Count Decodings of a Partially Masked Digit Stream
A noisy channel emits a digit string in which some positions are masked as '*', meaning any digit 1-9. Letters map A=1..Z=26. Count how many original messages could decode to the stream.
Problem
Given a string s of digits and the wildcard '*' (which represents any digit from 1 to 9), where '1'->'A', ..., '26'->'Z', count the number of ways to decode s into letters. Return the count modulo 1e9 + 7.
Input
A string s consisting of digits 0-9 and '*'.
Output
An integer: the number of decodings modulo 1e9 + 7.
Constraints
- 1 <= s.length <= 100000
- s consists of digits and '*'.
Examples
Example 1
Input
s = "*"
Output
9
'*' can be any of 1..9, decoding to A..I.
Example 2
Input
s = "1*"
Output
18
9 single-digit splits (1 then *) plus 9 two-digit (11..19).