91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

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

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
E 26), "VF" (22 6), or "BBF" (2 2 6).ded as “BZ” (2 26), “VF” (22 6), 
or “BBF” (2 2 6).xplanation: It could be decoded a`s "BZ" (2

First

類似于臺階問題，當兩個數(shù)字組成小于26且大于10時。字符串s[:i]的所有可能解碼方式等于s[:i-1]+s[:i-2].
使用dp數(shù)組存儲中間值，定義dp[i]為從0到i之間的所有解碼方式， 則dp[i] = dp[i-1] + dp[i-2]
此外，我們還需要對0值進行處理

1. 當字符s[i]等于'0'，且'0'的前面一位大于'2'。比如'30'，因為'30'無法編碼，所以返回0。
2. 當字符s[i]等于'0'，但前面一位小于'2'時，則只能讓'0'和前面一位進行編碼，因此可能方式等于dp[i-2]。
3. 當字符s[i-1]等于'0'時，由于'0'只能跟s[i-2]的字符匹配解碼，因此s[i]只能選擇單獨解碼或和s[i+1]共同解碼

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


s = Solution()
print(s.numDecodings(''))