Why my solution got TLE? (AC now, O(n) time and O(1) space)


  • 0
    F

    I came up with the following DP solution where a, b, c, d, e, f, g represent the number of strings that
    a: no A, end with one L
    b: no A, end with LL
    c: no A, end with P
    d: one A, end with one L
    e: one A, end with LL
    f: one A, end with P
    g: one A, end with A

    class Solution(object):
        def checkRecord(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n == 1:
                return 3
            m = 10**9 + 7
            a, b, c, d, e, f, g = 1, 1, 2, 1, 0, 1, 2
            for _ in xrange(2, n):
                # a, b, c, d, e, f, g = c, a, a+b+c, f+g, d, d+e+f+g, a+b+c
                a, b, c, d, e, f, g = c, a, (a+b+c)% m, (f+g)% m, d, (d+e+f+g)% m, (a+b+c)% m
            return (a+b+c+d+e+f+g) % m
    

  • 2

    Try this:

    class Solution(object):
        def checkRecord(self, n):
            """
            :type n: int
            :rtype: int
            """
            
            # TLE solution
            if n == 1:
                return 3
            m = 10**9 + 7
            a, b, c, d, e, f, g = 1, 1, 2, 1, 0, 1, 2
            for _ in xrange(2, n):
                a, b, c, d, e, f, g = c, a, (a+b+c)% m, (f+g)% m, d, (d+e+f+g)% m, (a+b+c)% m
            return (a+b+c+d+e+f+g) % m
    

    Just mod during the for loop.


  • 0
    F

    @fallcreek

    Thanks! Can you please explain why this works if possible?


  • 0

    @fungyh Keep number in range of int. Just a guess, if you don't mod your number during for loop, a, b, ... g will get very very large in the end, and cost more time during computation.


  • 0
    F

    @fallcreek
    Thanks, I always thought mod is a slow operation :(


Log in to reply
 

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