#639
Decode Ways II
international master · 1975 · lc hard +32 · verified · 31.7% accepted · 1,655 likes · top 9%
Description
Letters A–Z map to "1"–"26". A coded string s may contain digits 0–9 and the wildcard '*', which can stand for any digit 1–9. Count all valid ways to decode s back into letters (grouping digits as 1- or 2-digit codes that map to 1–26). Return the total modulo 109 + 7.
Example 1:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
Example 2:
Input: s = "*"
Output: 9
Explanation: The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9".
Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively.
Hence, there are a total of 9 ways to decode "*".
Example 3:
Input: s = "1*"
Output: 18
Explanation: The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19".
Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K").
Hence, there are a total of 9 * 2 = 18 ways to decode "1*".
Example 4:
Input: s = "2*"
Output: 15
Explanation: The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29".
"21", "22", "23", "24", "25", and "26" have 2 ways of being decoded, but "27", "28", and "29" only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode "2*".
Code
1
2
3