<p>You have intercepted a secret message encoded as a string of numbers. The message is <strong>decoded</strong> via the following mapping:</p>

<p><code>&quot;1&quot; -&gt; &#39;A&#39;<br />
&quot;2&quot; -&gt; &#39;B&#39;<br />
...<br />
&quot;25&quot; -&gt; &#39;Y&#39;<br />
&quot;26&quot; -&gt; &#39;Z&#39;</code></p>

<p>However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes (<code>&quot;2&quot;</code> and <code>&quot;5&quot;</code> vs <code>&quot;25&quot;</code>).</p>

<p>For example, <code>&quot;11106&quot;</code> can be decoded 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>
	<li>The grouping <code>(1, 11, 06)</code> is invalid because <code>&quot;06&quot;</code> is not a valid code (only <code>&quot;6&quot;</code> is valid).</li>
</ul>

<p>Note: there may be strings that are impossible to decode.<br />
<br />
Given a string s containing only digits, return the <strong>number of ways</strong> to <strong>decode</strong> it. If the entire string cannot be decoded in any valid way, return <code>0</code>.</p>

<p>The test cases are generated so that the answer fits in a <strong>32-bit</strong> integer.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;12&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>&quot;12&quot; could be decoded as &quot;AB&quot; (1 2) or &quot;L&quot; (12).</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;226&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>&quot;226&quot; could be decoded as &quot;BZ&quot; (2 26), &quot;VF&quot; (22 6), or &quot;BBF&quot; (2 2 6).</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;06&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p>&quot;06&quot; cannot be mapped to &quot;F&quot; because of the leading zero (&quot;6&quot; is different from &quot;06&quot;). In this case, the string is not a valid encoding, so return 0.</p>
</div>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>s</code> contains only digits and may contain leading zero(s).</li>
</ul>

// Time Complexity: O(N), where N is length of the string. Memoization helps in pruning the recursion tree and hence decoding for an index only once. Thus this solution is linear time complexity.

// Space Complexity: O(N). The dictionary used for memoization would take the space equal to the length of the string. There would be an entry for each index value. The recursion stack would also be equal to the length of the string.

class Solution {
public:
    map<int, int> memo; // Memoization map to store results of subproblems

    // Recursive function to count the number of ways to decode the substring starting from `index`
    int recursiveWithMemo(int index, string str) {
        // Check if this subproblem has already been solved
        if (memo.count(index)) {
            return memo[index];
        }

        // If we've reached the end of the string, there is exactly one way to decode it (i.e., an empty string is a valid decoding)
        if (index == str.size()) {
            return 1;
        }

        // If the current character is '0', it can't be decoded (invalid encoding)
        if (str[index] == '0') {
            return 0;
        }

        // If we're at the last character of the string, there's exactly one way to decode it (if it's not '0')
        if (index == str.length() - 1) {
            return 1;
        }

        // Initialize the number of ways to decode the substring from the current index
        int res = 0;

        // Decode the substring starting from the current index as a single digit
        res += recursiveWithMemo(index + 1, str);

        // Check if the next two characters form a valid number between 10 and 26 (inclusive)
        if (index + 1 < str.length() && stoi(str.substr(index, 2)) <= 26) {
            // If so, add the number of ways to decode the substring starting from `index + 2`
            res += recursiveWithMemo(index + 2, str);
        }

        // Save the result in the memoization map
        memo[index] = res;

        // Return the result for the current index
        return res;
    }

    // Function to start the recursive process and return the number of ways to decode the entire string
    int numDecodings(string s) {
        return recursiveWithMemo(0, s); // Start decoding from index 0
    }
};

// 简易版
// You have an encoding that maps each letter to a number
// A -> 0 B -> 1 ... K -> 10 ... U -> 20 ... Z -> 25
// given an encoded string e.g. '911', find the total number of possible encoding strings that can be generated.
// Example: '10' => ['BA', 'K'] => 2; '911' => ['JBB', 'JL'] => 2; '1' => ['B'] => 1

class Solution1 {
public:
    map<int, int> memo; // Memoization map to store results of subproblems

    // Recursive function to count the number of ways to decode the substring starting from `index`
    int recursiveWithMemo(int index, string str) {
        // Check if this subproblem has already been solved
        if (memo.count(index)) {
            return memo[index];
        }

        // If we've reached the end of the string, there is exactly one way to decode it (i.e., an empty string is a valid decoding)
        if (index == str.size()) {
            return 1;
        }

        // Initialize the number of ways to decode the substring from the current index
        int res = 0;

        // Decode the substring starting from the current index as a single digit
        res += recursiveWithMemo(index + 1, str);

        // Check if the next two characters form a valid number between 00 and 25 (inclusive)
        if (index + 1 < str.length()) {
            int twoDigitNumber = stoi(str.substr(index, 2));  // Get the two-digit number
            if (twoDigitNumber <= 25) {
                // If so, add the number of ways to decode the substring starting from `index + 2`
                res += recursiveWithMemo(index + 2, str);
            }
        }

        // Save the result in the memoization map
        memo[index] = res;

        // Return the result for the current index
        return res;
    }

    // Function to start the recursive process and return the number of ways to decode the entire string
    int numDecodings(string s) {
        return recursiveWithMemo(0, s); // Start decoding from index 0
    }
};


// class Solution {
// public:
//     int numDecodings(string s) {
//         if (s.empty() || s[0] == '0') return 0;

//         int a = 1;
//         int b = 1;
        
//         for(int i = 1; i < s.size(); i++){
//             if(s[i-1] == '0') a = 0;
//             if(s[i] == '0') b = 0;
//             if(s[i-1] == '1' || s[i-1] == '2' && s[i] <= '6'){
//                 int sum = a + b;
//                 a = b;
//                 b = sum;
//             } else {
//                 a = b;
//             }
//         }
//         return b;
//     }
// };


class Solution4 {
public:
    int numDecodings(string str) {
        if(str.size() == 0 || str == "") return 0;
        int size = str.size();
        vector<int> dp(str.size() + 1, 0);
        dp[0] = 1;
        dp[1] = str[0] == '0'? 0 : 1;
        for(int i = 2; i <= size; i++) {
            string oneDigit = str.substr(i - 1, i);
            string twoDigit = str.substr(i - 2, i);
            if(oneDigit[0] > '0' && oneDigit[0] <= '9') {
                dp[i] += dp[i - 1];
            }
            if(twoDigit[0] == '1' ||  (twoDigit[0] == '2' && twoDigit[1] <= '6')) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[size];
        
    }
};

// Efficiency: This approach is efficient as long as the range of days is manageable, as it avoids using complex data structures like heaps.
// Readability: The logic is straightforward, focusing on attending the earliest possible day, making it easy to understand.
// This method ensures that you always choose the earliest available day within the event's time frame, maximizing the number of events you can attend!
12700