Python, Straightforward DP with Explanation

• At time t where every report is length t, Let `a, b, c` be sequence types without an 'A' ending in N, NL, LL; and `d,e,f` be sequence types with an 'A' ending in N, NL, LL. (Here, N will denote a non-'L' character.) These types are disjoint, and exhaustive (their union is the set of all valid reports.) At the beginning when t = 1, `a = b = d = 1` and we should compute N-1 more steps.

From a sequence of type a, b, c, we can write an 'A' to give us a sequence of type d, or a 'P' to give us a sequence of type a. From a sequence of type d, e, f, we can write a 'P' to give us a sequence of type d. From a sequence of type a, b, d, e, we can write an 'L' to give a sequence of (respectively) b, c, e, f. These are all the letters we could write in any situation. Working backwards, we can get the sums for `a,b,c,d,e,f` written below.

``````def checkRecord(self, N):
MOD = 10**9 + 7
a = b = d = 1
c = e = f = 0
for _ in xrange(N-1):
a, b, c, d, e, f = (a+b+c)%MOD, a, b, (a+b+c+d+e+f)%MOD, d, e

return (a+b+c+d+e+f)%MOD
``````

• @awice Very nice solution, it's interesting that `N` could be `None`.

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