Decode Ways With Wildcards
Letters are encoded as 1 through 26. A message is a string of digits and the
character *, where * stands for any single digit from 1 to 9, never 0.
Count the ways to decode the message into letters, taking one or two characters at a time,
where a two-character group must read between 10 and 26 inclusive and a one-character
group must not be 0.
Print the count modulo 1000000007.
* -> 9 any of 1..9
1* -> 18 11..19 as one letter each, or 1 then any of 1..9
** -> 96
0 -> 0 a leading zero decodes to nothing
## Why this is not problem #402 with a substitution
#402 decodes a plain digit string. Adding * means each position stands for NINE possible
digits, and the count for a group is no longer 0 or 1 but a multiplicity.
Expanding the wildcards is impossible: n stars give 9^n strings. Instead the
multiplicities have to be counted directly, and the whole problem is the case analysis.
## The one-character group
s[i-1] == '*' -> 9 ways any of 1..9
s[i-1] == '0' -> 0 ways
otherwise -> 1 way
## The two-character group, in four cases
Write p for s[i-2] and c for s[i-1].
p = *, c = * -> 15 11..19 is 9, and 21..26 is 6
p = *, c digit -> 2 if c <= 6 else 1 1c always works, 2c only when c <= 6
p digit, c = * -> 9 if p = 1, 6 if p = 2, else 0
p digit, c digit -> 1 if 10 <= pc <= 26 else 0
## Where each number comes from
15 is the one to derive rather than memorise. A two-digit group from two stars must read
between 11 and 26, since neither digit can be 0: that is 11..19, nine values, plus
21..26, six values. 20 is excluded because the second star cannot be 0, and 10 for the
same reason.
2 if c <= 6 is 1c and 2c, and 2c is only in range when c is at most 6.
6 for p = 2 is 21..26, and 0 for p >= 3 because 3c exceeds 26 for every c.
Each of those is a small count that is easy to be one out on, which is why the reference outputs here were checked by EXPANDING every star to each of 1 through 9 and decoding the resulting plain strings directly. That oracle shares no logic with the case analysis, which is the only way to be confident in numbers like 15 and 96.
## Boundaries
0 answers 0, and *0 answers 2: the 0 cannot stand alone, so it must join the star,
giving 10 or 20, which is 2.
That input is the sharpest test in the set. It is the only one where a two-character group is the ONLY option, and a solution that handles the one-character case first and returns early gets it wrong.
*1 answers 11: the star alone gives 9 ways followed by 1, plus 11 and 21 as single
letters, which is 9 + 2.
## Cost
Time O(n). Space O(1) with two running values.