class Solution(object):
    mem={}
    for i in range(0,27):
        if i<=10 or i%10==0:
            mem[str(i)]=1
        else:
            mem[str(i)]=2
    mem['0']=0
    mem['00']=0
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if '00' in s or s[0]=='0':
            return 0

        if s in self.mem:
            return self.mem[s]
        count=0
        c1=0
        c1=self.numDecodings(s[1:])
        c2=0
        self.mem[s[1:]]=c1
        if int(s[:2])<=26:
            c2=self.numDecodings(s[2:])
            self.mem[s[2:]]=c2
        count+=c1+c2
        #print(s,count)
        return count