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

旧城等待， 2022-06-03 06:41 130阅读 0赞

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深度优先遍历][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;
        }
    };

[leetcode 91. Decode Ways DP_DFS]: http://blog.csdn.net/jackzhang_123/article/details/77943849

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_动态规划_中等_91. 解码方法

目录 1.题目 2.思路 3.代码实现（Java） 1.题目一条包含字母 A-Z 的消息通过以下映射进行了编码： 'A' -> "

女爷i/ 2023年10月06日 23:03/ 0 赞/ 68 阅读

相关 Decode Ways（C++解码方法）

（1）递归，超时 class Solution { public: int helper(string &s,int l) {

以你之姓@/ 2022年10月12日 01:03/ 0 赞/ 160 阅读

相关 leetcode 91. Decode Ways | 91. 解码方法（动态规划）

题目 [https://leetcode.com/problems/decode-ways/][https_leetcode.com_problems_decode-wa

不念不忘少年蓝@/ 2022年09月06日 00:17/ 0 赞/ 215 阅读

相关 [leetcode] 91. Decode Ways

91. Decode Ways 题目 A message containing letters from A-Z is being encoded to numbe

小灰灰/ 2022年06月17日 10:08/ 0 赞/ 187 阅读

相关 [leetcode] 91. Decode Ways

91. Decode Ways A message containing letters from A-Z is being encoded to numbers usin

一时失言乱红尘/ 2022年06月13日 03:27/ 0 赞/ 169 阅读

相关 leetcode 63. Unique Paths II DP动态规划

Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. Ho

爱被打了一巴掌/ 2022年06月09日 11:42/ 0 赞/ 224 阅读

相关 [Leetcode][python]Decode Ways/解码方法

题目大意现在有如下的字母与数字的对应关系：1-A, 2-B, …26-Z。给定一个由数字组成的字符串，判断按照上面的映射可以转换成多少种不同的字符串。解题思路

冷不防/ 2022年06月06日 04:13/ 0 赞/ 180 阅读

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

A message containing letters from A-Z is being encoded to numbers using the following ma

旧城等待，/ 2022年06月03日 06:41/ 0 赞/ 131 阅读

相关 LeetCode 91.Decode Ways (解码方法)

题目描述：一条包含字母 `A-Z` 的消息通过以下方式进行了编码： 'A' -> 1 'B' -> 2 ... 'Z' -> 26 给定

男娘i/ 2022年05月10日 10:22/ 0 赞/ 210 阅读

相关 LeetCode : 91. Decode Ways j解码方式

试题 A message containing letters from A-Z is being encoded to numbers using the followi

悠悠/ 2021年06月24日 16:12/ 0 赞/ 371 阅读