解码方法 1&2

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 1.3k | 阅读时间 ≈ 5

解码方法1

题目描述

https://leetcode-cn.com/problems/decode-ways/
一条包含字母 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 只包含数字，并且可能包含前导零。

解题思路

一开始写了好多if else，结果总有通不过的用例。看了题解真的简洁明了，只需要考虑两种情况：第一种是只考虑当前字符；另外一种考虑当前字符和前面一个字符。其实有些像加上了一些判断条件的爬楼梯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        if (n == 0) return 0;
        dp[0] = 1;
        for (int i = 1; i <=n ; i++){
            if (s[i-1] != '0')
                dp[i] += dp[i-1];
            if (i > 1 && s[i-2] != '0' && (s[i-2]-'0')*10 + (s[i-1]-'0') <= 26)
                dp[i] += dp[i-2];
        }
        return dp[n];
    }
};

解码方法2

题目描述

https://leetcode-cn.com/problems/decode-ways-ii/
一条包含字母 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 取余 的结果。

示例 1：
输入：s = ““
输出：9
解释：这一条编码消息可以表示 “1”、”2”、”3”、”4”、”5”、”6”、”7”、”8” 或 “9” 中的任意一条。
可以分别解码成字符串 “A”、”B”、”C”、”D”、”E”、”F”、”G”、”H” 和 “I” 。
因此，”“ 总共有 9 种解码方法。

示例 2：
输入：s = “1“
输出：18
解释：这一条编码消息可以表示 “11”、”12”、”13”、”14”、”15”、”16”、”17”、”18” 或 “19” 中的任意一条。
每种消息都可以由 2 种方法解码（例如，”11” 可以解码成 “AA” 或 “K”）。
因此，”1“ 共有 9 * 2 = 18 种解码方法。

示例 3：
输入：s = “2“
输出：15
解释：这一条编码消息可以表示 “21”、”22”、”23”、”24”、”25”、”26”、”27”、”28” 或 “29” 中的任意一条。
“21”、”22”、”23”、”24”、”25” 和 “26” 由 2 种解码方法，但 “27”、”28” 和 “29” 仅有 1 种解码方法。
因此，”2“ 共有 (6 2) + (3 1) = 12 + 3 = 15 种解码方法。

提示：
1 <= s.length <= 105
s[i] 是 0 - 9 中的一位数字或字符 ‘*’

解题思路

这题有更多的情况，不过大致思路还是和解码方法1一样，考虑一个字符和两个字符。

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
class Solution {
public:
    static constexpr int mod = 1000000007;
    int numDecodings(string s) {
        auto check1digit = [](char c) -> int {
            if (c == '0')
                return 0;
            return c == '*' ? 9 : 1;
        };

        auto check2digit = [](char c0, char c1) -> int {
            if (c0 == '*' && c1 == '*')
                return 15;
            if (c0 == '*')
                return c1 <= '6' ? 2 : 1;
            if (c1 == '*'){
                return c0 == '1' ? 9 : c0 == '2' ? 6 : 0;
            }
            return c0 != '0' && (c0 - '0') * 10 + (c1 - '0') <= 26;
        };
        
        int n = s.size();
        if (n == 0) return 0;
        int pre2 = 0, pre1 = 1, curr = 0;
        for (int i = 1; i <=n ; i++){
            curr = (long long)pre1 * check1digit(s[i-1]) % mod;
            if (i > 1)
                curr = (curr + (long long)pre2 * check2digit(s[i-2],s[i-1])) % mod;
            pre2 = pre1;
            pre1 = curr;
        }
        return curr;
    }
};