Leetcode刷题记录——91. 解码方法

是一道极其基本的动态规划问题 需要注意的是如果str的首字母为0，可以直接在这个case下return 0的

动态规划要么像下面写法1一样写dict 要么像下面写法2这样偷懒，用lru_cache

写法1 老老实实写dict

#from functools import lru_cache class Solution: def __init__(self): self.idi = {'':1} #@lru_cache() def numDecodings(self, s: str) -> int: if s in self.idi: return self.idi[s] #if s == '': # return 1 elif s[0] == '0': self.idi[s] = 0 return 0 if len(s) == 1: self.idi[s] = 1 if s != '0' else 0 return 1 if s != '0' else 0 head = int(s[:2]) if head >= 10 and head <= 26: self.idi[s] = self.numDecodings(s[1:]) + self.numDecodings(s[2:]) return self.idi[s] else: self.idi[s] = self.numDecodings(s[1:]) return self.idi[s]

写法2 投机取巧用lru_cache

from functools import lru_cache class Solution: #def __init__(self): @lru_cache() def numDecodings(self, s: str) -> int: if s == '': return 1 elif s[0] == '0': return 0 if len(s) == 1: return 1 if s != '0' else 0 head = int(s[:2]) if head >= 10 and head <= 26: return self.numDecodings(s[1:]) + self.numDecodings(s[2:]) else: return self.numDecodings(s[1:])