L91 Decode Ways

#O(n)

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """        
        if s == '' or s == '0' or s[0] == '0':
            return 0

        dp = [1, 1]

        # '1261'
        # i: 0 1 2 3 4  
        #dp =1 1 2 3 3
        #idx   0 1 2 3
        #str=  1 2 6 1       
        for i in range(2, len(s) + 1):
            if int(s[i-2:i]) >= 10 and int(s[i-2:i]) <= 26 and s[i-1] != '0': # 
                dp.append(dp[i-2] + dp[i-1])
            elif int(s[i-2:i]) == 10 or int(s[i-2:i]) == 20:
                dp.append(dp[i-2])
            elif s[i-1] != '0':
                dp.append(dp[i-1])
            else:
                return 0

        return dp[len(s)]

#dp =1 1 2 3 3
#str=  1 2 6 1
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """        
        if s == '' or s[0] == '0':
            return 0

        dp = [1, 1]

        # '1261'
        for i in range(1, len(s)):
            if int(s[i-1:i+1]) >= 10 and int(s[i-1:i+1]) <= 26 and s[i] != '0':
                dp.append(dp[i-1] + dp[i])
            elif int(s[i-1:i+1]) == 10 or int(s[i-1:i+1]) == 20:
                dp.append(dp[i-1])
            elif s[i] != '0':
                dp.append(dp[i])
            else:
                return 0

        return dp[len(s)]

class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        MOD = 10 ** 9 + 7
        N = len(s)

        dp = [0] * (N+1)
        dp[0] = 1
        if s[0] == '*':
            dp[1] = 9
        else:
            dp[1] = 1 if s[0] != '0' else 0

        for i in range(1, N):
            if s[i] == '*':
                dp[i+1] = 9 * dp[i] % MOD
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + 9 * dp[i-1]) % MOD
                elif s[i-1] == '2':
                    dp[i+1] = (dp[i+1] + 6 * dp[i-1]) % MOD
                elif s[i-1] == '*':
                    dp[i+1] = (dp[i+1] + 15 * dp[i-1]) % MOD
            else:
                dp[i+1] = dp[i] if s[i] != '0' else 0
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + dp[i-1]) % MOD
                elif s[i-1] == '2' and int(s[i]) <= 6:
                    dp[i+1] = (dp[i+1] + dp[i-1]) % MOD
                elif s[i-1] == '*':
                    if int(s[i]) <= 6:
                        dp[i+1] = (dp[i+1] + 2 * dp[i-1]) % MOD
                    else:
                        dp[i+1] = (dp[i+1] + dp[i-1]) % MOD
        return dp[-1]

def decode(code): # bitwise or 
        def helper(prefix, code, s):
                # base case
                if len(code) == 0:
                        s.add(prefix)
                        return s

                if code[0] == '0':
                        return s
                # 1 char, if code[0] == '1'
                s |= helper(prefix + chr(int(code[0]) - 1 + ord('A')), code[1:], s)
                # 2 chars, if code[0:2] available
                if len(code) >= 2 and code[0] == '1': # '10' <= code[0:2] <= '19'
                        s |= helper(prefix + chr(int(code[:2]) - 1 + ord('A')), code[2:], s)
                if len(code) >= 2 and '20' <= code[0:2] <= '26':
                        s |= helper(prefix + chr(int(code[:2]) - 1 + ord('A')), code[2:], s)
                return s

        s = set()
        return helper("", code, s)

code = "126"
print (decode(code))