91. Decode Ways

"""91. Decode Ways, backtrack递归方法想了很久没想明白。看了discuss知道用dp，创建memo的list，每个index表示在当前所拥有的decode的方式。memo[0] = 1 一个empty string就只有一种decode的方法.memo[1]，表示当string的size为一时有多少种decode的方法。从index = 2 开始遍历，每次回溯1 or 2 个 substring 如果符合要求就累加到当前位。最后返回memo第n位
"""
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0

        n = len(s)
        memo = [0] * (n+1)
        memo[0] = 1
        memo[1] = 1 if s[0] != '0' else 0

        for i in range(2, n+1):
            first = int(s[i-1:i])
            second = int(s[i-2:i])

            if first >= 1 and first <= 9:
                memo[i] += memo[i-1]

            if second >= 10 and second <= 26:
                memo[i] += memo[i-2]

        return memo[n]