Python AC with 68ms


  • 0
    S

    Could make the code more clean?

    class Solution:
        def __init__(self):
            self.d = {}
        # @param s, a string
        # @return an integer
        def numDecodings(self, s):
            def num2(s):
                t = int(s)
                if t == 10 or t == 20 : return 1
                if t>10 and t<27: return 2
                elif t>=0 and t<10: return 0
                elif s[1]=='0': return 0
                else: return 1
            len_= len(s)
            if len_ == 0 or s[0] == '0' : return 0
            if len_ == 1 : return 1
            if len_ == 2 : return num2(s)
            tmp = s[-2:]
            t = num2(tmp)
            if not self.d.has_key(len_-2): self.d[len_-2] = self.numDecodings(s[:-2])
            if not self.d.has_key(len_-1): self.d[len_-1] = self.numDecodings(s[:-1])
            if t == 1 :
                if tmp[1] == '0': return self.d[len_-2]
                return self.d[len_-1]
            elif t == 2: 
                return self.d[len_-2] + self.d[len_-1]
            else: 
                if tmp[1] == "0": return 0
                else: return self.d[len_-1]

  • 0
    S
    class Solution:
        # @param s, a string
        # @return an integer
        def numDecodings(self, s):
            if s[0:1]=='0' or len(s) == 0:
                return 0
            res = list()
            sum = 1
            count = 0
            max = 0
            i = 1
            length = len(s)
            while i<length:
                if s[i-1:i]=='0':
                    return 0
                t = int(s[i-1:i+1])
                if s[i:i+1]!='0' and t >= 10 and t <= 26:
                    count += 1
                elif s[i:i+1]=='0':
                    if t==10 or t==20:
                        if count != 0:
                            res.append(count)
                            if count > max:
                                max = count
                            count = 0
                        if i+2 <= length:
                            if s[i+1:i+2]=='0':
                                return 0
                        i += 1
                    else:
                        return 0
                else:
                    if count != 0:
                        res.append(count+1)
                        if count+1 > max:
                            max = count+1
                        count = 0
                i += 1
            if count != 0:
                res.append(count+1)
                if count+1 > max:
                    max = count+1
            fab = [None]*(max + 3)
            fab[1] = 1
            fab[2] = 2
            if max > 2:
                for i in range(3,max+1):
                    fab[i] = fab[i-1] + fab[i-2]
            for x in res:
                sum *= fab[x]
            return sum
    

    52ms


  • 0
    S

    It`s Fabonacci Number in fact.


Log in to reply
 

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