I'm currently working on the Student Attendance Record II problem:
Given a positive integer \$n\$, return the number of all possible attendance records with length \$n\$, which will be regarded as rewardable. The answer may be very large, return it after
mod 109 + 7
.A student attendance record is a string that only contains the following three characters:
'A' : Absent. 'L' : Late. 'P' : Present.
A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
The idea is to use Dynamic Programming to use the results for smaller n
to calculate the results of bigger n
. I'm currently keeping two lists - one to track L
and P
and the other - to track A
:
MODULO = 10 ** 9 + 7
class Solution(object):
def checkRecord(self, n):
lates = [[0, 0, 0], [1, 1, 0]] + [[0, 0, 0] for _ in xrange(2, n + 1)]
absences = [[0, 0, 0], [1, 0, 0]] + [[0, 0, 0] for _ in xrange(2, n + 1)]
for i in xrange(2, n + 1):
last_late_row = lates[i - 1]
last_late_row_sum = last_late_row[0] + last_late_row[1] + last_late_row[2]
last_absence_row = absences[i - 1]
last_absence_row_sum = last_absence_row[0] + last_absence_row[1] + last_absence_row[2]
lates[i] = last_late_row_sum % MODULO, last_late_row[0], last_late_row[1]
absences[i] = ((last_late_row_sum + last_absence_row_sum) % MODULO, last_absence_row[0], last_absence_row[1])
return (sum(lates[n]) + sum(absences[n])) % MODULO
The code works, but it does not pass the Time Limit requirements for big n
. Even though, for n = 100000
LeetCode OJ runs it for only ~220ms.
How would you recommend to improve on running time?