题目描述

包含 A-Z 的字母的消息通过以下规则编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个包含数字的编码消息，请确定解码方法的总数。

例如，给定消息为 "12"，它可以解码为 "AB"（1 2）或 "L"（12）。

"12" 的解码方法为 2 种。

注意：这里的‘0’是不编码的，所以说就有可能出现断层，导致编码数为0，例如：当出现“01”时，由于第一个元素就是为‘0’所以就没办法往后继续计数了（二位组合的01不代表编码1，所以01也没有意义）。这里题目没说，太坑了。

我的解法——DP（AC）

其中dp(i)表示s[0]到s[i-1]这一共i个字符组成的子串编码个数。
当前状态可能从上一个、上上个转移过来
注意：初始边界情况、各种if太难想了，根本做不到bug free
复杂度O(n)
结果：Beat61.37%

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

        return dp[length - 1]