Python


  • 0
    B
        def checkRecord(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n == 0: return 0
            if n == 1: return 3
            M = 1000000007
            dp = [0 for j in range (3)] 
            tmp = [0 for j in range (3)]
            dpsum = [0 for i in range(n)]
            #First calculate only P and up to 2 L combinations
            dp[0] = 1 #1 p
            dp[1] = 1 #0p 1L
            dp[2] = 0 # 2L not possible for initial value of only one character
            dpsum[0] = sum(dp)
            for i in range(1,n):
                tmp[0] = (dp[0] + dp[1] + dp[2])%M
                tmp[1] = dp[0]        
                tmp[2] = dp[1]
                dp = tmp[:]
                dpsum[i] = sum(dp)
            retVal = (dpsum[-1])
    
            retVal += 2 * (dpsum[n-2]) %M
            for i in range(1, n-1):
                #insert 'A' one-by-one at every location by breaking the 
                #original list into two and lookup and multiply the total 
                #combinations of the two broken lists from the dpsum list. 
                retVal += (dpsum[i-1] * dpsum[n-2-i])%M 
            return retVal%M
    

Log in to reply
 

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