Decode Ways

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = {len(s) : 1}

        def dfs(i):
            if i in dp:
                return dp[i]
            if s[i] == "0":
                return 0

            numMappings = dfs(i + 1)

            if (i + 1 < len(s) and (s[i] == "1" or (s[i] == "2" and s[i+1] in "0123456"))):
                numMappings += dfs(i + 2)

            dp[i] = numMappings
            return numMappings

        return dfs(0)