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).

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     def numDecodings(self, s):
         """
         :type s: str
         :rtype: int
         """
         if not s:
             return 0
         
         def num_decode(i):
             # Number of ways to decode s[i:]
             if i == len(s):
                 return 1
 
                 
             if i not in memo:                
                 num_ways = 0
                 
                 if s[i] in single_digit_codes:
                     num_ways += num_decode(i + 1)
 
                 if s[i:i+2] in double_digit_codes:
                     num_ways += num_decode(i + 2)
             
                 memo[i] = num_ways
             return memo[i]
         single_digit_codes = set(str(x) for x in range(1, 10))
         double_digit_codes = set(str(x) for x in range(10, 27))
         memo = {}
         return num_decode(0)

class Solution:
     def numDecodings(self, s):
         """
         :type s: str
         :rtype: int
         """
         if not s: return 0
         cipher = dict((str(k+1),v) for k,v in
                       enumerate("abcdefghijklmnopqrstuvwxyz"))
         # funhash = dict((str(k),1) for k,v in cipher.items())
         funhash = {"":1}
         def helpRec(s):
             if s in funhash: return funhash[s]
             r1 = 0
             if s[0] in cipher:
                 r1 = helpRec(s[1:])
             r2 = 0
             if len(s) >= 2 and s[:2] in cipher:
                 r2 = helpRec(s[2:])
             rval = r1 + r2
             funhash[s] = rval
             # print(s,rval)
             return rval
         return helpRec(s)
             


class Solution:
     def numDecodings(self, s):
         """
         :type s: str
         :rtype: int
         """ 
         if s == None or len(s) == 0:
             return 0
             
         def in10(c):
             return c.isdigit() and c>'0' and c<='9'
         def in26(c):
             return c.isdigit() and c>='10' and c<='26'
         
         
         memo = [0 for _ in range(len(s))]
         if in10(s[0]):
             memo[0] = 1 
         
         for i in range(1, len(s)):
             if i == 1:
                 if in10(s[i]):
                     memo[i] = memo[i-1]
                 if in26(s[:2]):
                     memo[i] = memo[i] + 1
             else:
                 if in10(s[i]):
                     memo[i] += memo[i-1]
                 if in26(s[i-1:i+1]):
                     memo[i] += memo[i-2]
                     
         
         return memo[-1]
             
             
         
         


class Solution:
     def numDecodings(self, s):
         """
         :type s: str
         :rtype: int
         """
         alphabet = 'abcdefghijklmnopqrstuvwxyz'
         char_code = {k:str(v) for k, v in zip(alphabet, list(range(1, 27)))}
         code_char = {v:k for k, v in list(char_code.items())}
         def numDecodingsHelper(s, hist={}):
             if not s: return 0
             if len(s) == 1: return 1 if s in code_char else 0
             if len(s) == 2:
                 tmp = 1 if s in code_char else 0
                 return tmp + numDecodingsHelper(s[0]) * numDecodingsHelper(s[1])
             if s[1:] not in hist:
                 hist[s[1:]] = numDecodingsHelper(s[1:], hist)
             current1 = hist[s[1:]] if s[:1] in code_char else 0
             if s[2:] not in hist:
                 hist[s[2:]] = numDecodingsHelper(s[2:], hist)
             current2 = hist[s[2:]] if s[:2] in code_char else 0
             return current1 + current2
         return numDecodingsHelper(s, {})