[力扣 91] [leetcode 91] 解码方法 2021.9.27

2023-12-20 10:41:04

题目描述

一条包含字母 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" 在映射中并不等价。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。

题目数据保证答案肯定是一个 32 位的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

示例 4：

输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

提示：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

回溯法，遍历所有的可能性。
动态规划，这个题目有些像70 爬楼梯

尝试1 回溯法

关于回溯法可以参考Carl哥的回溯算法精讲。

由于s只包含数字字符，所以每一个字符有两种选择：

跳到下一个字符
跳到下一个字符的下一个字符。（当此字符与下一个字符的值 <= 26 且不等于 10, 20 时）

有如下代码：

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0')
            return 0;
        int num_decodings                     = 0;
        std::function<void(int)> backtracking = [&](int index) {
            if (index == s.size()) {
                num_decodings++;
                return;
            }
            char this_char = s[index];
            if (this_char == '0') {
                return;
            }

            char next_char = 0;
            if (index + 1 < s.size()) {
                next_char = s[index + 1];
            }

            // 含有下一个元素
            // 走一步
            if (next_char != 0 && next_char == '0') {
                backtracking(index + 2);
            } else {
                backtracking(index + 1);
            }
            // 走两步
            if (next_char != 0) {
                if ((this_char == '1' && next_char >= '1' && next_char <= '9') ||
                    (this_char == '2' && next_char >= '1' && next_char <= '6')) {
                    backtracking(index + 2);
                }
            }
        };

        backtracking(0);
        return num_decodings;
    }
};

失败1

遇到测试用例
"111111111111111111111111111111111111111111111" 会超时，想想也是啦！

解决办法

这样做总会遇到一些重复统计的事情。比如字符串
"9999132699"
在26处会出现分支。"2699"的次数会被[1,3]，[13]重复统计。

解决办法得想办法把后面的状态都保存起来。或者加快回溯的速度。
使用容器修改一下

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0')
            return 0;
        int num_decodings = 0;

        std::vector<int> index_stack;
        index_stack.push_back(0);
        bool all_end = false;
        while (!all_end) {
            all_end = true;
            printf("stack size : %lu\n", index_stack.size());
            std::vector<int> pushing;
            for (auto it = index_stack.begin(); it != index_stack.end(); it++) {
                // 每次更新这个stack的最后位数字。
                // 如果遇到2这种情况再复制一下之前的数字走2
                if (*it == s.size() || s[*it] == '0') {
                    continue;
                }
                all_end = false;

                int current_index = *it;
                char this_char    = s[current_index];
                char next_char    = 0;
                if (current_index + 1 < s.size()) {
                    next_char = s[current_index + 1];
                }
                if (next_char != 0 && next_char == '0') {
                    *it = current_index + 2;
                } else {
                    *it = current_index + 1;
                }

                // 走两步
                if (next_char != 0) {
                    if ((this_char == '1' && next_char >= '1' && next_char <= '9') ||
                        (this_char == '2' && next_char >= '1' && next_char <= '6')) {
                        pushing.push_back(current_index + 2);
                    }
                }
            }
            index_stack.insert(index_stack.end(), pushing.begin(), pushing.end());
        }

        int end_count = 0;
        for (auto &d : index_stack) {
            if (d == s.size())
                end_count++;
        }
        return end_count;
    }
};

失败2

"111111111111111111111111111111111111111111111" 会超时
使用上面代码有如下打印：

stack size : 1
stack size : 2
stack size : 4
stack size : 8
stack size : 16
stack size : 32
stack size : 64
stack size : 128
stack size : 256
stack size : 512
stack size : 1024
stack size : 2048
stack size : 4096
stack size : 8192
stack size : 16384
stack size : 32768
stack size : 65536
stack size : 131072
stack size : 262144
stack size : 524288
stack size : 1048576
stack size : 2097152
stack size : 4194304
stack size : 8388607
stack size : 16776938
stack size : 33541203
stack size : 66850129
stack size : 131425006
stack size : 249013925
stack size : 440732113
...

题解1

参考1
学习一下如在递归中使用map加快速度。

尝试2 DP

dp table的定义及意义
dp[i] 表示当字符串i为字符终点时所表示的编码方法总数。

递推公式
110 共有1种方法[1,10]
如何状态转移？

dp[2] 处有0时怎么办？
1. 如果前一个字符不是0，则为dp[0]
2. 如果是字符0，则为0
dp[2] 与前面的字符凑成26需要把前面的dp[1] + 1 且后一个字符不能是0
所以有：

if nums[i] == '0':
    if nums[i-1] == '0':
        return 0
    else:
        dp[i] = dp[i-1];
else:
    if ((nums[i-1] == '1' && nums[i] >= '1' && nums[i] <= '9') or 
       (nums[i-1] == '2' && nums[i] >= '1' && nums[i] <= '6"'))  and 
        (nums[i+1] != '0'):
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = dp[i-1]

初始化顺序
dp[0] = 1;
遍历顺序
由于后面的值需要用到前面的值。所以从前向后。

有如下代码：

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0')
            return 0;
        std::vector<int> dp(s.size(), 0);
        dp[0] = 1;
        for (int i = 1; i < s.size(); i++) {
            char pre_char  = s[i - 1];
            char this_char = s[i];
            char next_char = 0;
            if (i + 1 < s.size()) {
                next_char = s[i + 1];
            }
            if (this_char == '0') {
                if (pre_char == '0') {
                    // 不能解析直接return
                    return 0;
                }
                dp[i] = dp[i - 1];
            } else {
                if ((next_char != 0 && next_char == '0') || pre_char == '0') {
                    // 不能向前扩展变成两个字符
                    dp[i] = dp[i - 1];
                } else if ((pre_char == '1' && this_char >= '1' && this_char <= '9') ||
                           (pre_char == '2' && this_char >= '1' && this_char <= '6')) {
                    dp[i] = dp[i - 1] + 1;
                } else {
                    dp[i] = dp[i - 1];
                }
            }
        }
        return dp[s.size() - 1];
    }
};

自测失败1

261101756562

问题分析

226 有三种方式[2,2,6] , [22,6] , [2,26]
1. [2,2,6]
2. [22,6
3. [2,26]
261101756562 有四种方式
1. 2,6,1,10,1,7,5,6,5,6,2
2. 26 ,1,10,1,7,5,6,5,6,2
3. 26, 1,10,17,5,6,5,6,2
4. 2,6,1,10,17,5,6,5,6,2
1111 有五种方式
1. 1，1，1，1
2. 11，1，1
3. 1，11，1
4. 1，1，11
5. 11，11
111111
1. 1,1,1,1,1,1
2. 11,1,1,1,1
3. 1,11,1,1,1
4. 1,1,11,1,1
5. 1,1,1,11,1
6. 1,1,1,1,11
7. 11,11,1,1
8. 11,1,11,1
9. 11,1,1,11
10. 1,11,11,1
11. 1,11,1,11
12. 1,1,11,1,1
13. 1,1,11,11

按照此dp的方法，1-4是可以输出的，但是第五个是输出不了的。
如果前面有一个两个可以结合，那么如果本例可以两个结合。
所以此递推公式不适用。

尝试3 DP

dp table的意义
以i为终点的字符串解码方法的总数
递推公式

思路还是不对。

题解1

参考1
参考2
参考3

教训

这个题解在分情况讨论的时候会考虑到前面的多项与本项之前的关系，而我考虑的只有前面的项。
下次在做DP问题时，可以考虑本项与前面每一项，或者某一项的关系。

看到第三题解的时候发现自己还是没有融会贯通 70 爬格子的问题。
每次只需把 dp[i-1] 与 dp[i-2]的做和就是总数了。

希望可以给大家一些参考。

码农公寓