Decode Ways

Problem: Decode Ways

When we are dealing a new digit, we can decode it with the previous as a number between 10 ~ 26, or as a single number between 1 ~ 9. Thus, ways of decoding are decided by last two results.

Code in Python:

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == "": return 0
        if s[0] == "0": return 0
        dp = []
        for i in xrange(len(s)):
            if i == 0: dp.append(1)
            elif s[i] == "0":
                if int(s[i-1:i+1]) > 26 or int(s[i-1:i+1]) < 1: return 0
                dp.append(dp[i-2])
            elif int(s[i-1:i+1]) <= 26 and s[i-1] != "0": dp.append(dp[i-1] + dp[i-2])
            else: dp.append(dp[i-1])
        return dp[-1]