leetcode 639. Decode Ways II 解码方法+动态规划DP+无论如何也不会做-蒲公英云

leetcode 639. Decode Ways II 解码方法+动态规划DP+无论如何也不会做

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:
Input: “*”
Output: 9
Explanation: The encoded message can be decoded to the string: “A”, “B”, “C”, “D”, “E”, “F”, “G”, “H”, “I”.
Example 2:
Input: “1*”
Output: 9 + 9 = 18
Note:
The length of the input string will fit in range [1, 105].
The input string will only contain the character ‘*’ and digits ‘0’ - ‘9’.

下面这种解法是论坛上排名最高的解法，常数级的空间复杂度，写法非常简洁，思路也巨牛逼，博主是无论如何也想不出来的，只能继续当搬运工了。这里定义了一系列的变量e0, e1, e2, f0, f1, f2。其中：

e0表示当前可以获得的解码的次数，当前数字可以为任意数 (也就是上面解法中的dp[i])

e1表示当前可以获得的解码的次数，当前数字为1

e2表示当前可以获得的解码的次数，当前数字为2

f0, f1, f2分别为处理完当前字符c的e0, e1, e2的值

那么下面我们来进行分类讨论，当c为星号的时候，f0的值就是9*e0 + 9*e1 + 6*e2，这个应该不难理解了，可以参考上面解法中的讲解，这里的e0就相当于dp[i-1]，e1和e2相当于两种不同情况的dp[i-2]，此时f1和f2都赋值为e0，因为要和后面的数字组成两位数的话，不会增加新的解码方法，所以解码总数跟之前的一样，为e0, 即dp[i-1]。

当c不为星号的时候，如果c不为0，则f0首先应该加上e0。然后不管c为何值，e1都需要加上，总能和前面的1组成两位数；如果c小于等于6，可以和前面的2组成两位数，可以加上e2。然后我们更新f1和f2，如果c为1，则f1为e0；如果c为2，则f2为e0。

最后别忘了将f0，f1，f2赋值给e0，e1，e2，其中f0需要对超大数取余

本题建议和leetcode 91. Decode Ways DP动态规划+DFS深度优先遍历

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
using namespace std;
class Solution 
{
public:
    int numDecodings(string s) 
    {
        long e0 = 1, e1 = 0, e2 = 0, f0, f1, f2, M = 1e9 + 7;
        for (char c : s)
        {
            if (c == '*')
            {
                f0 = 9 * e0 + 9 * e1 + 6 * e2;
                f1 = e0;
                f2 = e0;
            }
            else
            {
                f0 = (c > '0') * e0 + e1 + (c <= '6') * e2;
                f1 = (c == '1') * e0;
                f2 = (c == '2') * e0;
            }
            e0 = f0 % M;
            e1 = f1;
            e2 = f2;
        }
        return e0;
    }
};