动态规划之解码方法
程序员文章站
2022-07-05 13:14:52
...
LeetCode 91. 解码方法
一条包含字母 A-Z 的消息通过以下方式进行了编码:
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串,请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
if n == 0: # 没有数字
return 0
if n == 1: # 单个数字
if s[0] == '0': # 0 不对应任何字符
return 0
else:
return 1
dp = [0] * (n + 1)
dp[0] = 1 # 一个字符初始化
for i in range(n):
# 当前字符单独作为一个解码单元时
# 更新dp[i + 1],如果当前字符为‘0’,那么无法解码,dp[i + 1]=0;否则,当前解码数先等于前面的解码数。
dp[i + 1] = 0 if s[i] == '0' else dp[i] # 第i个字符对应dp[i + 1],i从0到n-1
# 当前字符和前一个字符作为一个解码单元时
#如果前一个和当前数字构成的两位数满足11-26,则可以重新组合,那么组合数为前两个的组合数加上一个数的组合数。
if i > 0 and (s[i - 1] == '1' or (s[i - 1] == '2' and s[i] <= '6')):
dp[i + 1] += dp[ i - 1]
return dp[-1]