class Solution:
    def numDecodings(self, s: str) -> int:

        n = len(s)
        dp = [0]*(n+1)
        dp[0] = 1

        for i in range(1, n+1):
            for j in range(1, 27):
                c = str(j)
                if i-len(c)>=0 and c == s[i-len(c):i]:
                    dp[i] += dp[i-len(c)]

        return dp[-1]