//
// Created by 罗炳国 on 2023/12/28.
//

#ifndef PFJ_CODE039_NUMDECODINGS_H
#define PFJ_CODE039_NUMDECODINGS_H

#include "commonHeader.h"

/**
 * 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
 * 'A' -> "1"
 * 'B' -> "2"
 * ...
 * 'Z' -> "26"
 * 要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：
 * "AAJF" 对应分组 (1 1 10 6)
 * "KJF" 对应分组 (11 10 6)
 * 注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。
 * 除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息
 * 给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。
 * 由于答案数目可能非常大，返回 109 + 7 的 模 。
 * 639.https://leetcode.cn/problems/decode-ways-ii/
 * */

class code039_numDecodings {
    int mod = 1000000007;
public:
    int numDecodings1(string s) {
        return process(s, 0);
    }

    int process(string &s, int index) {
        int N = s.size();
        long ans = 0;
        if (N == index)
            return 1;

        // 单转
        if (s[index] == '0')
            return 0;
        long p1 = process(s, index + 1);
        if (s[index] == '*')
            ans += 9 * p1;
        else
            ans = p1;

        // 和下个位置一起转
        if (index < N - 1) {
            long p2 = process(s, index + 2);
            if (s[index] == '*') {
                if (s[index + 1] == '*') {
                    ans += 15 * p2;
                } else if (s[index + 1] - '0' < 7) // 第一个*可以变1和2
                    ans += 2 * p2;
                else // 第一个*只能变1
                    ans += p2;
            } else {
                // 第一位不是*
                if (s[index] - '0' == 1) {
                    // 第二位是*
                    if (s[index + 1] == '*') {
                        ans += 9 * p2;
                    } else { //1x
                        ans += p2;
                    }
                } else if (s[index] - '0' == 2) {
                    // 第二位是*
                    if (s[index + 1] == '*') {
                        ans += 6 * p2;
                    } else if ((s[index] - '0') * 10 + s[index + 1] - '0' <= 26)
                        ans += p2;
                }
            }
        }
        return ans % mod;
    }

    int numDecodings2(string s) {
        int N = s.size();
        vector<int> dp(N + 1, -1);
        return process(s, 0, dp);
    }

    int process(string &s, int index, vector<int> &dp) {
        int N = s.size();
        long ans = 0;
        if (N == index)
            return 1;

        if (dp[index] != -1)
            return dp[index];
        // 单转
        if (s[index] == '0')
            return 0;
        long p1 = process(s, index + 1, dp);
        if (s[index] == '*')
            ans += 9 * p1;
        else
            ans = p1;

        // 和下个位置一起转
        if (index < N - 1) {
            long p2 = process(s, index + 2, dp);
            if (s[index] == '*') {
                if (s[index + 1] == '*') {
                    ans += 15 * p2;
                } else if (s[index + 1] - '0' < 7) // 第一个*可以变1和2
                    ans += 2 * p2;
                else // 第一个*只能变1
                    ans += p2;
            } else {
                // 第一位不是*
                if (s[index] - '0' == 1) {
                    // 第二位是*
                    if (s[index + 1] == '*') {
                        ans += 9 * p2;
                    } else { //1x
                        ans += p2;
                    }
                } else if (s[index] - '0' == 2) {
                    // 第二位是*
                    if (s[index + 1] == '*') {
                        ans += 6 * p2;
                    } else if ((s[index] - '0') * 10 + s[index + 1] - '0' <= 26)
                        ans += p2;
                }
            }
        }
        dp[index] = ans % mod;
        return dp[index];
    }

    int numDecodings3(string s) {
        int N = s.size();
        vector<long> dp(N + 1, 0);
        dp[N] = 1;

        if (s[N - 1] == '0')
            dp[N - 1] = 0;
        else if (s[N - 1] == '*')
            dp[N - 1] = 9;
        else
            dp[N - 1] = 1;
        for (int i = N - 2; i >= 0; i--) {
            if (s[i] == '0') {
                dp[i] = 0;
                continue;
            }
            // 单转
            if (s[i] == '*') {
                dp[i] = dp[i + 1] * 9 % mod;
            } else {
                dp[i] = dp[i + 1] % mod;
            }

            //和后面一位一起转
            int tmp = 0;
            if (s[i] == '*') {
                if (s[i + 1] == '*') { // 11-19 21 - 26
                    tmp = 15 * dp[i + 2] % mod;
                } else if (s[i + 1] - '0' < 7) { // 两种变法：1x 2x
                    tmp = 2 * dp[i + 2] % mod;
                } else { // 7 8 9 第一个*只能变为1->1x
                    tmp = dp[i + 2] % mod;
                }
            } else if (s[i] - '0' <= 2) { // 1x 2x
                if (s[i + 1] == '*') {
                    if (s[i] == '1')
                        tmp = 9 * dp[i + 2] % mod;
                    else // s[i] == '2'
                        tmp = 6 * dp[i + 2] % mod;
                } else {
                    if ((s[i] - '0') * 10 + s[i + 1] - '0' < 27)
                        tmp = dp[i + 2] % mod;
                }
            }
            dp[i] += tmp;
        }
        return dp[0] % mod;
    }

    int numDecodings4(string s) {
        int N = s.size();
        long ppre = 1, pre, ans;

        if (s[N - 1] == '0')
            pre = 0;
        else if (s[N - 1] == '*')
            pre = 9;
        else
            pre = 1;
        ans = pre;
        for (int i = N - 2; i >= 0; i--) {
            if (s[i] == '0') {
                ans = 0;
                ppre = pre;
                pre = ans;
                continue;
            }
            // 单转
            if (s[i] == '*') {
                ans = pre * 9 % mod;
            } else {
                ans = pre % mod;
            }

            //和后面一位一起转
            if (s[i] == '*') {
                if (s[i + 1] == '*') { // 11-19 21 - 26
                    ans += 15 * ppre % mod;
                } else if (s[i + 1] - '0' < 7) { // 两种变法：1x 2x
                    ans += 2 * ppre % mod;
                } else { // 7 8 9 第一个*只能变为1->1x
                    ans += ppre % mod;
                }
            } else if (s[i] - '0' <= 2) { // 1x 2x
                if (s[i + 1] == '*') {
                    if (s[i] == '1')
                        ans += 9 * ppre % mod;
                    else // s[i] == '2'
                        ans += 6 * ppre % mod;
                } else {
                    if ((s[i] - '0') * 10 + s[i + 1] - '0' < 27)
                        ans += ppre % mod;
                }
            }
            ppre = pre;
            pre = ans;
        }
        return ans % mod;
    }
    void test() {
        string s("7");
        int ans = numDecodings4(s);
        std::cout << s << ":" << ans << endl;
    }
};

#endif//PFJ_CODE039_NUMDECODINGS_H