利用python 完成leetcode 91 解碼方法

一條包含字母 A-Z 的消息通過以下方式進行了編碼：

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

給定一個隻包含數字的非空字元串，請計算解碼方法的總數。

示例 1:

輸入: “12”

輸出: 2

解釋: 它可以解碼為 “AB”（1 2）或者 “L”（12）。

示例 2:

輸入: “226”

輸出: 3

解釋: 它可以解碼為 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

思路

動态規劃，建立數組dp，dp[i]表示前i+1個字母有多少種解碼方法，

前i個字母最後一個單詞有兩種選擇，取倒數兩個字母為一個單詞或者一個字母為一個單詞

如果s[i]可以解碼dp[i]=dp[i]+dp[i-1]

如果s[i-1:i+1]可以解碼dp[i]=dp[i]+dp[i-2]

代碼

def numDecodings(self, s):
    l=[]
    for i in range(1,27):l.append(str(i))
    dp=[0]*(len(s))
    if(s[0]in l):dp[0]=1
    for i in range(1,len(s)):
        a=0
        b=0
        if(s[i]in l):a=dp[i-1]
        if  s[i-1:i+1] in l:
            if(i==1):b=1
            else: b=dp[i-2]
        dp[i]=a+b
    return dp[-1]