decodeWays.py

"""
 Leetcode 91. Decode ways 
 Method used : Memoization 
"""


defcheck(s,mp): # Checks if the string is a valid number in the map of numbers
returnint(sinmp.keys())
g_d=dict()
classSolution():
defhelper(self,s,mp):
if(sing_d):
returng_d[s]
if(s[0] =='0'): # if the string starts with 0, you cannot decode
return0
if(len(s) ==2): # len(s) == 2; two cases : checking two characters(s[0] && s[1]) seperately and the s[0:2] 
returncheck(s[0:2],mp) +self.helper(s[1:],mp)
if(len(s) ==1 ): 
returnint(sinmp.keys())
"""
 There are two cases 
 * Pick one character from the front 
 * Check if the charcater chosen is valid
 * Pick two character from the front
 * Check if the charcater chosen is valid
 the conditions below help to validate the conditions mentioned here.
 """
ifnotcheck(s[0:2],mp) andcheck(s[0:1],mp):
g_d[s] =self.helper(s[1:],mp)
returng_d[s]
ifnotcheck(s[0:1],mp) andcheck(s[0:2],mp):
g_d[s] =self.helper(s[2:],mp)
returng_d[s]
g_d[s] =self.helper(s[1:],mp) +self.helper(s[2:],mp)

returng_d[s]
defnumDecodings(self, s):
"""
 :type s: str
 :rtype: int
 """
mp=dict()
foriinrange(1,27):
mp[str(i)] =chr(64+i)
# print(mp)
returnself.helper(s,mp)