Leetcode 91. Decode Ways

https://leetcode.com/problems/decode-ways/

Using DP. Actually this solution still has the space to improve: because the current state is only related with two indexes before, so rolling DP will improve the space to O(1).

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param s, a string
    # @return an integer
    def numDecodings(self, s):
        if s=="" or s[0]=='0': return 0
        dp=[1,1]
        for i in range(2,len(s)+1):
            if 10 <=int(s[i-2:i]) <=26 and s[i-1]!='0':
                dp.append(dp[i-1]+dp[i-2])
            elif int(s[i-2:i])==10 or int(s[i-2:i])==20:
                dp.append(dp[i-2])
            elif s[i-1]!='0':
                dp.append(dp[i-1])
            else:
                return 0
        return dp[len(s)]

Run Time: 76 ms