91. 解码方法

发表于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 5 分钟

如果说，2～3 个月前，这种题我是不可能做出来的，不知道你信不信，现在总算是稍微觉得经过自己努力我也可以做出来了。看来这个还需要坚持和训练，就可以克服的。

先来看题目：

一条包含字母 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 只包含数字，并且可能包含前导零。

  1. 解码方法 <– 传送门

首先来分析一下题目，这是一个简单的映射，就是把序号映射成字母，但是，数字串有多种划分的方法，因为 26 个字母，有 1 位数，也有 2 位数。

对于一个字符串来说，一次解码 1 个数字，或者加码两个数字，要求总的分割次数，但是不关心每种分割的具体排列。其实，看到这里基本上就是“动态规划”算法无疑了，特征太过明显了。

当然，回溯法来穷举的话还是很直观的，经不住诱惑我还是试了一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numDecodings(self, s: str) -> int:
        self.s = s
        self.n = len(s)
        self.cnt = 0
        self.dfs(0)
        return self.cnt
    
    def dfs(self, start: int):
        if start == self.n:
            self.cnt += 1
            return
        if start < self.n:
            num = int(self.s[start:start + 1])
            if 1 <= num <= 26:
                self.dfs(start + 1)
        if num != 0 and start < self.n - 1:
            num = int(self.s[start:start + 2])
            if 1 <= num <= 26:
                self.dfs(start + 2)

很好写，很直观，从前向后，尝试一次解码一个数字，或者一次解码两个数字。可惜这个算法会超时。这个算法的时间复杂度是多少呢？我这样分析，一个递归体里，有两个分支，第一个分支，一个一个字符解码，所以深度是 n 层，另一个分支，两个两个字符解码，是 n / 2 层。 整个递归树在内存展开会是一个二叉树，最大深度是 n 层，所以时间复杂度是 O(2^n)，字符串的长度最大 100，最还情况下，2 的 100 次方这个规模量级，难怪 AC 不了。

还是要老老实实“动态规划”的。然后，我就想到一道经典题目，很像，就是说，一个人上楼梯，一次可以上一阶，也可以一次上两阶，请问登上 n 阶台阶的方法数。这题目是一次解码一个字母，或者一次解码两个字母，解码 n 个字母。你看简直一毛一样。区别就是，1 ~ 26 这个限制而已，所以，其实状态方程我们法已经知道了，就是 f(n) = f(n - 1) + f(n - 2)，无非不能这么单纯地去做个加法，而是要去判断条件约束，如果不满足，就不能往上加。

剩下就是细节了。不过细节真的是魔鬼，我给大家看看我第一次写 AC 的代码：

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
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * n

        if s[0] == '0':
            return 0
        
        dp[0] = 1

        if n == 1:
            return dp[0]
        
        if s[1] != '0': 
            if 1 <= int(s[:2]) <= 26:
                dp[1] = 2
            else:
                dp[1] = 1
        else:
            if 1 <= int(s[:2]) <= 26:
                dp[1] = 1
            else:
                return 0
        

        for i in range(2, n):
            if s[i] != '0':
                dp[i] += dp[i - 1]
            else:
                if 1 <= int(s[i - 1:i + 1]) <= 26:
                    pass
                else:
                    return 0
            if s[i - 1] != '0' and 1 <= int(s[i - 1:i + 1]) <= 26:
                dp[i] += dp[i - 2]
        return dp[n - 1]

丑陋不堪，无以言表啊，怎么会写成这个样子呢？我的立足点，其实是分析最后一个字符合法，以及最后两个字符合法，都满足的话，那么 f(i) = f(i - 1) + f(i - 2)，否则只能是其中一项有效。其中 f(i - 1) 有效的条件是，第 i 个字符不为 0，f(i - 2)，有效的条件是最后两个字符不是 0 开头，而且 小于等于 26。

虽然难看，好歹解出来了，对比了官方解后，开始反思，到底为什么写到这么难看。其实，根本原因是搞错了边界，我用 i 代表字符下标，所以，假设的是至少有一个字符，第一个字符的下标是 0。题目的提示里也说，length 的取值范围是 1 到 100。等于是被这个东西误导了。就算长度是从 1 开始，但是算法推演，为什么不能从 0 开始呢？根本就是无关的两件事情嘛。

如果从 0 开始推演，重写这个算法：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1

        for i in range(1, n + 1):
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]
            if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
                dp[i] += dp[i - 2]
        return dp[n]

妈呀，竟然能简洁这么多！！这个写法跟上面不同在于，i 代表的是“待解码串”的长度。长度为 0 的时候，只有 1 种解码方法，就是空串。因为 i 这回代表的是长度了，所以换算下标的时候，就要 -1 了。

所以，这道题里面，最平凡的情况 f(0) = 1 这个条件，却十分不显然。成为我写对这个算法的障碍。其实写到这里，观察到我们只依赖 f(i-1) 和 f(i-2) 不难把整个 dp 数组优化成两个变量以优化空间复杂度，不过考虑到 lenght 只有 100，优化空间只有 800 字节的内存占用，其实也没什么优化的意义。

官方解有优化过的，大家也可以自己动手，我就不继续贴代码了。