80. LeetCode.91. 解码方法

• 标签： 动态规划
• 难度： 中等

---

• 题目描述

• 解法

此题的递推式跟LeetCode70.爬楼梯 一样： dp[i] = dp[i-1] + dp[i-2], 本以为可以秒杀的题，却提交了 5 次之后才 ac, 代码写得还很丑。 其实题目暗含了如下 2 个约束条件：

1. 0 或 以 0 作为高位的解码不是有效解码.
2. 编码后的值在 [1,26] 区间

这种题如果在面试中碰到了，在时间有限的情况下心态就贼容易崩啊.

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        s = map(int, s)
        dp = [0]* len(s)
        if s[0] > 0:
            dp[0] = 1
            if len(s) == 1:
                return dp[0]
            if 1<= (s[0]*10 + s[1]) <= 26:
                dp[1] += 1
            if s[1] > 0:
                dp[1] += 1
       
        for i in range(2, len(s)):
            if s[i]>0:
                dp[i] += dp[i-1]
            if (s[i-1]>0) and (1<= (s[i-1]*10 + s[i]) <= 26) :
                dp[i] += dp[i-2]

        return dp[-1]
               

• 其他解法

暂略。