跳至主要內容

0091. 解码方法

ITCharge大约 3 分钟

0091. 解码方法open in new window

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

题目链接

题目大意

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

  • A 映射为 11
  • B 映射为 22
  • ...
  • Z 映射为 2626

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

  • "AAJF",将消息分组为 (11106)(1 1 10 6)
  • "KJF",将消息分组为 (11106)(11 10 6)

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

说明

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

示例

  • 示例 1:
输入:s = "226"
输出:3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6)

解题思路

思路 1:动态规划

1. 划分阶段

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

2. 定义状态

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

3. 状态转移方程

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

  1. 使用了一个字符,对 s[i]s[i] 进行翻译。只要 s[i]!=0s[i] != 0,就可以被翻译为 A ~ I 的某个字母,此时方案数为 dp[i]=dp[i1]dp[i] = dp[i - 1]
  2. 使用了两个字符,对 s[i1]s[i - 1]s[i]s[i] 进行翻译,只有 s[i1]!=0s[i - 1] != 0,且 s[i1]s[i - 1]s[i]s[i] 组成的整数必须小于等于 2626 才能翻译,可以翻译为 J ~ Z 中的某字母,此时方案数为 dp[i]=dp[i2]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]=1dp[0] = 1
  • 字符串只有一个字符时,需要考虑该字符是否为 00,不为 00 的话,dp[1]=1dp[1] = 1,为 00 的话,dp[0]=0dp[0] = 0
5. 最终结果

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

思路 1:动态规划代码

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)
  • 空间复杂度O(n)O(n)。用到了一维数组保存状态,所以总体空间复杂度为 O(n)O(n)