乐趣区

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
退出移动版