跳转至

解码方法 II⚓︎

Leetcode题目链接

描述⚓︎

详见中文题目链接。

解答⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private:
    const static long long mod = 1e9 + 7;
public:
    int numDecodings(string s) {
        int n = s.length();
        long long current = 0LL, nxt = 1LL, nxtNxt = 0LL;

        for (int i = n - 1; i >= 0; i--) {
            if (s[i] != '0') {
                current = nxt * (s[i] == '*' ? 9 : 1);

                if (i + 1 < n) {
                    if (s[i] != '*') {
                        if (s[i + 1] != '*') {
                            if (stoi(s.substr(i, 2)) <= 26) current += nxtNxt;
                        } else {
                            if (s[i] == '1') current += nxtNxt * 9;
                            else if (s[i] == '2') current += nxtNxt * 6;
                        }
                    } else {
                        if (s[i + 1] != '*') {
                            if (s[i + 1] <= '6') current += nxtNxt * 2;
                            else current += nxtNxt;
                        } else current += nxtNxt * 15;
                    }
                }

                current %= mod;
            }

            nxtNxt = nxt;
            nxt = current;
            current = 0;
        }

        return static_cast<int>(nxt);
    }
};