A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2:
Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
My code:
#import numpy as np
class Solution:
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if len(s)==0:
return 0
for i in range(len(s)):
if i==0 and s[i]=='0':
return 0
if i>0 and s[i]=='0' and s[i-1]!='1' and s[i-1]!='2':
return 0
self.record=[-1 for i in range(len(s))]
count=self.check_possible(s,len(s)-1)
#print(self.record)
return int(count)
def check_possible(self,s,i):
if i==0:
return 1
if i==1:
if int(s[:i+1])<=26 and s[i]!='0':
return 2
return 1
if self.record[i]!=-1:
return self.record[i]
count1=0
if s[i]!='0':
count1=self.check_possible(s,i-1)
count2=0
if int(s[i-1:i+1])<=26 and s[i-1]!='0':
count2=self.check_possible(s,i-2)
self.record[i]=count1+count2
return self.record[i]