<p>A message containing letters from <code>A-Z</code> can be <strong>encoded</strong> into numbers using the following mapping:</p>

<pre>
&#39;A&#39; -&gt; &quot;1&quot;
&#39;B&#39; -&gt; &quot;2&quot;
...
&#39;Z&#39; -&gt; &quot;26&quot;
</pre>

<p>To <strong>decode</strong> an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, <code>&quot;11106&quot;</code> can be mapped into:</p>

<ul>
	<li><code>&quot;AAJF&quot;</code> with the grouping <code>(1 1 10 6)</code></li>
	<li><code>&quot;KJF&quot;</code> with the grouping <code>(11 10 6)</code></li>
</ul>

<p>Note that the grouping <code>(1 11 06)</code> is invalid because <code>&quot;06&quot;</code> cannot be mapped into <code>&#39;F&#39;</code> since <code>&quot;6&quot;</code> is different from <code>&quot;06&quot;</code>.</p>

<p><strong>In addition</strong> to the mapping above, an encoded message may contain the <code>&#39;*&#39;</code> character, which can represent any digit from <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code> (<code>&#39;0&#39;</code> is excluded). For example, the encoded message <code>&quot;1*&quot;</code> may represent any of the encoded messages <code>&quot;11&quot;</code>, <code>&quot;12&quot;</code>, <code>&quot;13&quot;</code>, <code>&quot;14&quot;</code>, <code>&quot;15&quot;</code>, <code>&quot;16&quot;</code>, <code>&quot;17&quot;</code>, <code>&quot;18&quot;</code>, or <code>&quot;19&quot;</code>. Decoding <code>&quot;1*&quot;</code> is equivalent to decoding <strong>any</strong> of the encoded messages it can represent.</p>

<p>Given a string <code>s</code> consisting of digits and <code>&#39;*&#39;</code> characters, return <em>the <strong>number</strong> of ways to <strong>decode</strong> it</em>.</p>

<p>Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;*&quot;
<strong>Output:</strong> 9
<strong>Explanation:</strong> The encoded message can represent any of the encoded messages &quot;1&quot;, &quot;2&quot;, &quot;3&quot;, &quot;4&quot;, &quot;5&quot;, &quot;6&quot;, &quot;7&quot;, &quot;8&quot;, or &quot;9&quot;.
Each of these can be decoded to the strings &quot;A&quot;, &quot;B&quot;, &quot;C&quot;, &quot;D&quot;, &quot;E&quot;, &quot;F&quot;, &quot;G&quot;, &quot;H&quot;, and &quot;I&quot; respectively.
Hence, there are a total of 9 ways to decode &quot;*&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1*&quot;
<strong>Output:</strong> 18
<strong>Explanation:</strong> The encoded message can represent any of the encoded messages &quot;11&quot;, &quot;12&quot;, &quot;13&quot;, &quot;14&quot;, &quot;15&quot;, &quot;16&quot;, &quot;17&quot;, &quot;18&quot;, or &quot;19&quot;.
Each of these encoded messages have 2 ways to be decoded (e.g. &quot;11&quot; can be decoded to &quot;AA&quot; or &quot;K&quot;).
Hence, there are a total of 9 * 2 = 18 ways to decode &quot;1*&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;2*&quot;
<strong>Output:</strong> 15
<strong>Explanation:</strong> The encoded message can represent any of the encoded messages &quot;21&quot;, &quot;22&quot;, &quot;23&quot;, &quot;24&quot;, &quot;25&quot;, &quot;26&quot;, &quot;27&quot;, &quot;28&quot;, or &quot;29&quot;.
&quot;21&quot;, &quot;22&quot;, &quot;23&quot;, &quot;24&quot;, &quot;25&quot;, and &quot;26&quot; have 2 ways of being decoded, but &quot;27&quot;, &quot;28&quot;, and &quot;29&quot; only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode &quot;2*&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is a digit or <code>&#39;*&#39;</code>.</li>
</ul>

// This is Correct.
// 1D-DP + HashMap usage.

// class Solution {
//     unordered_map<string, int> decodeMap;
//     int MOD = 1e9 + 7;
//     void createDecodeMap() {
//         // Mapping for "1" to "26"
//         for (int i = 1; i <= 26; i++) {
//             decodeMap[to_string(i)] = 1;
//         }

//         // Mapping for "*0" to "*9"
//         for (int i = 0; i <= 9; i++) {
//             string key = "*" + to_string(i);
//             if (i == 7 || i == 8 || i == 9)
//                 decodeMap[key] = 1;
//             else
//                 decodeMap[key] = 2;
//         }

//         // Special cases for "*", "1*", "2*", "**"
//         decodeMap["*"] = 9;
//         decodeMap["1*"] = 9;
//         decodeMap["2*"] = 6;
//         decodeMap["**"] = 15;
//     }

// public:
//     int numDecodings(string s) {
//         createDecodeMap();

//         int n = s.length();
//         vector<long long> table((n + 1), 0);

//         table[0] = 1;
//         table[1] = decodeMap[s.substr(0, 1)];

//         for(int i = 2; i <= n; i++)
//         {
//             long long temp1 = decodeMap[s.substr((i - 1), 1)];
//             long long temp2 = decodeMap[s.substr((i - 2), 2)];

//             temp1 = (temp1 * table[i - 1]) % MOD;
//             temp2 = (temp2 * table[i - 2]) % MOD;

//             table[i] = (temp1 + temp2) % MOD;
//         }

//         return table[n];
//     }
// };


// 1D-DP only.

class Solution {
    int MOD = 1e9 + 7;

public:
    int numDecodings(string s) {
        int n = s.length();
        if (n == 0) return 0;

        long long prev2 = 1;  // dp[i-2]
        long long prev1 = (s[0] == '*') ? 9 : (s[0] != '0');  // dp[i-1]

        for (int i = 1; i < n; ++i) {
            long long curr = 0;

            // Check single character
            if (s[i] == '*') {
                curr = (prev1 * 9) % MOD;
            } else if (s[i] != '0') {
                curr = prev1;
            }

            // Check double characters
            if (s[i-1] == '*') {
                if (s[i] == '*') {
                    curr = (curr + prev2 * 15) % MOD; // "**" can be "11-19", "21-26"
                } else if (s[i] <= '6') {
                    curr = (curr + prev2 * 2) % MOD; // "*0-6" can be "10-16" or "20-26"
                } else {
                    curr = (curr + prev2 * 1) % MOD; // "*7-9" can be "17-19"
                }
            } else if (s[i-1] == '1') {
                if (s[i] == '*') {
                    curr = (curr + prev2 * 9) % MOD; // "1*" can be "11-19"
                } else {
                    curr = (curr + prev2) % MOD; // "10-19"
                }
            } else if (s[i-1] == '2') {
                if (s[i] == '*') {
                    curr = (curr + prev2 * 6) % MOD; // "2*" can be "21-26"
                } else if (s[i] <= '6') {
                    curr = (curr + prev2) % MOD; // "20-26"
                }
            }

            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
};
13918