Leetcode91-解码方法-Python实现

• 题目要求：

• 思路：

  • 动态规划，遍历字符串
  • 如果当前字符 s[i]+ 前一个字符 s[i-1]转换成数字后，在 10 与 26 之间，那么当前字符的解码方法数为 s[i-2]（两个字符前）的方法数。
  • 如果当前字符 s[i]转换成数字后，不为 0，那么当前字符的方法数要再加上 s[i-1]（前一个字符）的方法数。
  • 如果 s[0]和 s[0:2]都合法，那么 f(s[:])=f(s[1:])+f(s[2:])
  • 如果 s[0]合法而 s[0:2]不合法的话，那么 f(s[:])=f(s[1:])
  • 如 s[0]都不合法，那么不可能存在编码
• 核心代码：

# dp 初始化为[1,1]
dp = [1,1]
# 遍历字符串
for i in range(1,len(s)):
    # 当前字符的方法初始化为 0
    res = 0
    # 如果当前字符和前一个字符组合起来在 10-26 之间
    if int(s[i-1:i+1]) >= 10 and int(s[i-1:i+1]) <= 26:
        # 当前字符的方法数就等于前两个字符的方法数，这里写“=”和“+=”都是一样的
        res += dp[i-1]
    # 如果当前字符串不为 0
    if int(s[i]) != 0:
        # 那么当前字符的方法数需要加上前一个字符的方法数
        res += dp[i]
    # 把这个结果 append 到 dp 中       
    dp.append(res)
# 返回最后的结果即可
return dp[-1]

• 如果测试用例是 100：

  • 那么首先遍历到第一个 0
  • 这时 10 是有效的字符，而 0 不是，所以第一个 0 的方法数为 1
  • 遍历到第二个 0，00 不是有效的字符，0 也不是有效的，所以第二个 0 的方法数为 0
  • 也就是 dp 的最后一位为 0，最后返回的编码结果也是 0
• 需要注意一下 dp 中的方法数和字符下标的对应关系，dp[1]对应的是 s[0]的方法数
• 初始化 dp 为 [1,1] 是因为，默认 s[0:2]是合法的，如果合法，方法数加上 dp[0]，如果不合法，不使用 dp
• 完整代码：

class Solution:
    def numDecodings(self, s: str) -> int:
        if s == "" or int(s[0]) == 0:
            return 0
        dp = [1,1]
        for i in range(1,len(s)):
            res = 0
            if int(s[i-1:i+1]) >= 10 and int(s[i-1:i+1]) <= 26:
                res += dp[i-1]
            if int(s[i]) != 0:
                res += dp[i]
            dp.append(res)
        return dp[-1]

• 降低了空间复杂度：

class Solution:
    def numDecodings(self, s: str) -> int:
        if s == "" or int(s[0]) == 0:
            return 0
        pre, cur = 1, 1
        for i in range(1, len(s)):
            tmp = 0
            if int(s[i - 1:i + 1]) <= 26 and int(s[i - 1: i + 1]) >= 10:
                tmp += pre
            if int(s[i]) != 0:
                tmp += cur
            pre, cur = cur, tmp
        return cur