Python solution with explanation


  • 0
    S
    class Solution(object):
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            # the number of decodings for s[0...k] (inclusive) is num[k]
            # and it can be expressed by s[0...k-1] or s[0...k-2] depending on 
            # whether we choose to combine the last two characters
            self.mod = 10 ** 9 + 7
            self.memorytwo = {}
            if not s or s[0] == '0':
                return 0
            n = len(s)
            num = [0] * n; 
            if s[0] == '*':
                num[0] = 9
            else:
                num[0] = 1
            for k in range(1, n):
                num[k] = 0
                # not combine
                if s[k] != '0':
                    if s[k] == '*':
                        num[k] = num[k - 1] * 9 % self.mod
                    else:
                        num[k] = num[k - 1]
                # combine
                t = self.numDecodingsOfTwo(s[k-1:k+1])
                if t > 0:
                    if k == 1:
                        num[k] += t
                    else:
                        num[k] += t * num[k-2]
                    num[k] =  num[k] % self.mod
                    
            return num[n - 1]
                                              
                                
        def numDecodingsOfTwo(self, s):
            """
            Given s of two characters, find the num of decodings if we combine the two characters
            """
            if s[0] == '0':
                return 0
            if s in self.memorytwo:
                return self.memorytwo[s]
            # two '*'
            if s[0] == '*' and s[1] == '*':
                self.memorytwo[s] = 15
                return 15 #11--19, 21--26
            # one '*'
            if s[0] == '*':
                if s[1] <= '6':
                    self.memorytwo[s] = 2
                    return 2    # * can be 1 or 2
                else:
                    self.memorytwo[s] = 1
                    return 1    # * can only be 1
            if s[1] == '*':
                num = 0
                for i in range(1, 10):  # test * from 1 to 9
                    if 1 <= 10 * int(s[0]) + i <= 26:
                        num += 1
                self.memorytwo[s] = num
                return num
            # no '*'
            r = 1 if 1 <= int(s) <= 26 else 0
            self.memorytwo[s] = r
            return r
    

    Here please note that we can easily turn the space complexity into O(1) since we only depend on the previous two values of num. Instead of storing the whole num of length n, just store its latest two values.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.