LeetCode Decode Ways

LeetCode解題之Decode Ways

原題

現在有如下的字母與數字的對應關系：1-A, 2-B, …26-Z。給定一個由數字組成的字符串，判斷按照上面的映射可以轉換成多少種不同的字符串。

注意點：

例子：

輸入: s = “12”

輸出: 2（包括”AB”(1 2)和”L”(12)）

解題思路

第一感覺就是動態規劃，先寫了一個從前往後的版本，要復雜的分類要論，代碼很亂，後來發現從後開始遍歷更加容易。來看一下遞推式，假設原先的字符串為”y231”，現在在它之前加一個數字得到”xy231”，如果x不為0，此時，如果”xy”不在1-26之間，那麼原先能轉換的種類不變，只是在每個字符串之前增加一個x轉換後的字母；如果”xy”在1-26之間，那麼除了在原先每個字符串之前增加x轉換後的字母，還可能是在”231”轉化之後的字符串前增加”xy”轉化的字母。那如果x等於0呢，此時是一個非法字符串，讓它默認為0。但不能跳出循環，因為在前面繼續增加數字可能將字符串變為合法的。

AC源碼

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


if __name__ == "__main__":
    assert Solution().numDecodings("110") == 1
    assert Solution().numDecodings("40") == 0