A message containing the letters A-Z is encoded as follows:

'A' -> 1
'B' -> 2
...
'Z' -> 26

To decode an encoded message, all digits must be grouped and then mapped back to letters according to the original encoding scheme. There may be multiple ways to do this. For example, "11106" can be mapped as follows:

• "AAJF" corresponds to the grouping (1 1 10 6)
• "KJF" corresponds to the grouping (11 10 6)

Note that a grouping such as (1 11 06) is invalid because "06" cannot be mapped to 'F': "6" and "06" are different.

In addition to the digit-to-letter mapping described above, the encoded message may contain the character '*', which can represent any digit from '1' to '9' (but not '0'). For example, the encoded string "1*" can represent any of "11", "12", "13", "14", "15", "16", "17", "18", or "19". Decoding "1*" means counting the decodings of every encoded message it can represent.

Given a string s consisting of digits and the character '*', return the number of ways to decode it.

Because the number of ways may be very large, return the result modulo 109 + 7.

Example 1:

Input:s = "*"
Output:9
Explanation:This encoded message can represent any of "1", "2", "3", "4", "5", "6", "7", "8", or "9".
They can be decoded into "A", "B", "C", "D", "E", "F", "G", "H", and "I", respectively.
Therefore, "*" has 9 possible decodings.

Example 2:

Input:s = "1*"
Output:18
Explanation:This encoded message can represent any of "11", "12", "13", "14", "15", "16", "17", "18", or "19".
Each message can be decoded in 2 ways (for example, "11" can be decoded as "AA" or "K").
Therefore, "1*" has 9 * 2 = 18 possible decodings.

Example 3:

Input:s = "2*"
Output:15
Explanation:This encoded message can represent any of "21", "22", "23", "24", "25", "26", "27", "28", or "29".
"21", "22", "23", "24", "25", and "26" each have 2 decodings, while "27", "28", and "29" each have only 1 decoding.
Therefore, "2*" has (6 * 2) + (3 * 1) = 12 + 3 = 15 possible decodings.

Constraints:

• 1 <= s.length <= 105
• s[i] is a digit from 0 - 9 or the character '*'

Approach

#

This problem mainly tests the rigor of the reasoning.

The information in the statement makes it clear that this is a one-dimensional dynamic-programming problem. The idea is also a standard dynamic-programming recurrence: dp[i] is the number of ways to decode all strings formed by the first i characters of s.

• If s[i] is not ‘0’, it can form a decoding on its own, so dp[i + 1] += dp[i].
• If s[i - 1] and s[i] can form a number greater than or equal to 10 (this is a major pitfall because “01” is invalid) and less than or equal to 26, we can treat the two digits as one decoding, so dp[i + 1] += dp[i - 1].

The idea is simple, but the implementation is complicated because it is easy to overlook various cases, such as the fact that "*" can represent only 1 through 9 and “01” is not a valid number.

The main strategy is to split the cases. For s[i] and s[i-1], there are four cases depending on whether each is "*". Handling them separately avoids omissions.

C++ Code

#

using ll = int64_t;
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        ll dp[n + 1];
        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '*') dp[i + 1] += dp[i] * 9;
            else if (s[i] != '0') dp[i + 1] += dp[i];
            if (i > 0) {
// cout << "Good";
                if (s[i - 1] == '*' && s[i] != '*'){
                    if (s[i] <= '6') dp[i + 1] += 2 * dp[i - 1];
                    else dp[i + 1] += dp[i - 1];
                } else if (s[i - 1] == '*' && s[i] == '*') {
                    // cout << "Good";
                    dp[i + 1] += dp[i - 1] * 15;
                } else if (s[i - 1] != '*' && s[i] == '*') {
                    if (s[i - 1] == '1') dp[i + 1] += dp[i - 1] * 9;
                    else if (s[i - 1] == '2') dp[i + 1] += dp[i - 1] * 6;
                } else {
                    if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6'))
                        dp[i + 1] += dp[i - 1];
                }
            }
            dp[i + 1] %= ll(1e9 + 7);
        }
        return dp[n];
    }
};