Python O(n) time O(1) space solution, easy to understand

  • 0
    def checkRecord(self, n):
            :type n: int
            :rtype: int
            x: number of ways does not include A
            y: number of ways include A
            consider following stituation:
            xxxP: x[i-1]+y[i-1]
            xxxA: x[i-1]
            xxPL: x[i-2]+y[i-2]
            xxAL: x[i-2]
            xPLL: x[i-3]+y[i-3]
            xALL: x[i-3]
            x[i] = x[i-1]+x[i-2]+x[i-3]
            y[i] = y[i-1]+x[i-1]+y[i-2]+x[i-2]+y[i-3]+x[i-3]
            if n == 1:
                return 3
            x1,x2,x3 = 1,2,4
            y1,y2,y3 = 0,1,4
            for i in range(3,n+1):
                t = y3
                y3 = (x1+x2+x3+y1+y2+y3)%(10**9+7)
                y1 = y2
                y2 = t
                t = x3
                x3 = (x1+x2+x3)%(10**9+7)
                x1 = x2
                x2 = t
            return (x3+y3)%(10**9+7)

Log in to reply

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