Jianbo Dai's

lc091.解码方法

 
  • Mar 27, 2021

题目链接

类似于斐波那契数列的那种动态规划？方案数？或者是像上阶梯的方案数一类的题目？dp感觉状态转移还比较好搞清楚，就是要在各种情况的分类讨论搞清楚之后，那就不困难了。这个算法的时间复杂度是O（N），空间复杂度是O（N）。

python:

class Solution:
    def numDecodings(self, s: str) -> int:
        if s.startswith('0'): # 开头有‘0’直接返回
            return 0
        
        n = len(s)
        dp = [1] * (n + 1) # 重点是dp[0],dp[1] = 1, 1
        for i in range(2, n + 1):
            if s[i - 1] == '0' and s[i - 2] not in '12': # 出现前导‘0‘的情况，不能解码，直接返回
                return 0
            if s[i-2:i] in ['10', '20']: # 只有组合在一起时才能解码
                dp[i] = dp[i-2]
            elif '10' < s[i-2:i] <= '26': # 有两种解码方式
                dp[i] = dp[i-1] + dp[i-2]
            else: # ’01‘到‘09’或>'26'，只有单独才能解码
                dp[i] = dp[i-1]
        return dp[n]
Search