0091. 解码方法 #

标签：字符串、动态规划
难度：中等

题目大意 #

描述：给定一个数字字符串 s。该字符串已经按照下面的映射关系进行了编码：

A 映射为 1。
B 映射为 2。
…
Z 映射为 26。

基于上述映射的方法，现在对字符串 s 进行「解码」。即从数字到字母进行反向映射。比如 "11106" 可以映射为：

"AAJF"，将消息分组为 (1 1 10 6)。
"KJF"，将消息分组为 (11 10 6)。

要求：计算出共有多少种可能的解码方案。

说明：

$1 \le s.length \le 100$。
s 只包含数字，并且可能包含前导零。
题目数据保证答案肯定是一个 32 位的整数。

示例：

1
2
3


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

解题思路 #

思路 1：动态规划 #

1. 划分阶段 #

按照字符串的结尾位置进行阶段划分。

2. 定义状态 #

定义状态 dp[i] 表示为：字符串 s 前 i 个字符构成的字符串可能构成的翻译方案数。

3. 状态转移方程 #

dp[i] 的来源有两种情况：

使用了一个字符，对 s[i] 进行翻译。只要 s[i] != 0，就可以被翻译为 A ~ I 的某个字母，此时方案数为 dp[i] = dp[i - 1]。
使用了两个字符，对 s[i - 1] 和 s[i] 进行翻译，只有 s[i - 1] != 0，且 s[i - 1] 和 s[i] 组成的整数必须小于等于 26 才能翻译，可以翻译为 J ~ Z 中的某字母，此时方案数为 dp[i] = dp[i - 2]。

这两种情况有可能是同时存在的，也有可能都不存在。在进行转移的时候，将符合要求的方案数累加起来即可。

状态转移方程可以写为：

$dp[i] += \begin{cases} \begin{array} \ dp[i-1] & s[i] \ne 0 \cr dp[i-2] & s[i-1] \ne 0，s[i-1:i] \le 26 \end{array} \end{cases}$

4. 初始条件 #

字符串为空时，只有一个翻译方案，翻译为空字符串，即 dp[0] = 1。
字符串只有一个字符时，需要考虑该字符是否为 0，不为 0 的话，dp[1] = 1，为 0 的话，dp[0] = 0。

5. 最终结果 #

根据我们之前定义的状态，dp[i] 表示为：字符串 s 前 i 个字符构成的字符串可能构成的翻译方案数。则最终结果为 dp[size]，size 为字符串长度。

思路 1：动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def numDecodings(self, s: str) -> int:
        size = len(s)
        dp = [0 for _ in range(size + 1)]
        dp[0] = 1
        for i in range(1, size + 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[size]

思路 1：复杂度分析 #

时间复杂度：$O(n)$。一重循环遍历的时间复杂度是 $O(n)$。
空间复杂度：$O(n)$。用到了一维数组保存状态，所以总体空间复杂度为 $O(n)$。