class Solution:
    def numDecodings(self, s: str) -> int:
        if not s:
            return 0

        if s[0] == "0":
            return 0

        # dp[i] = (dp[i-1], contain this word) + (dp[i-1], contain two word)
        dp = [1, 1]

        for i, c in enumerate(s):
            ans_contain_this_word = 0
            if self.is_valid(s[i]): # dp[i-1] + i, check if 0
                ans_contain_this_word += (dp[-1])

            if i > 0 and self.is_valid_2(s[i-1:i+1]): # dp[i-2] + i-1,i
                ans_contain_this_word += (dp[-2])

            dp.append(ans_contain_this_word)

        return dp[-1]

    def is_valid_2(self, s):
        if s[0] == 0:
            return False

        return 10 <= int(s) <= 26

    def is_valid(self, s):
        return 1 <= int(s) <= 9