python实现leetcode之91. 解码方法

解题思路

如果是空字符串，有一种解码方案，解码也是空
如果以0开头，是无效的方案
如果长度为1并且不是以0开头，有一种方案
否则，长度>=2,此时前两个数字字符转整数
如果小于等于26，有两种选择，先解决第一个或者先解决前两个
如果大于26，先解决第一个字符，再解决剩下的字符

添加缓存避免重复计算

91. 解码方法

代码

class Solution:
    def numDecodings(self, s: str) -> int:
        return helper(s, {})

def helper(s, cache):
    if not s: return 1
    if s[0] == '0': return 0
    if len(s) == 1: return 1
    if s in cache: return cache[s]
    if int(s[0:2]) > 26:
        cache[s] = helper(s[1:], cache)
    else:
        cache[s] = helper(s[1:], cache) + helper(s[2:], cache)
    return cache[s]