Short Python solution with running time above 99%


  • 0
    P

    Basically we track how many times merge on two consecutive elements happens using variable m. We use variable values to hold generate values with True representing 1.

    Is there a way to shrink the storage O(n)?

    class Solution(object):
        def magicalString(self, n):
            """
            :type n: int
            :rtype: int
            """
            values, m, i = [False]*(n+1), 1, 3
            values[0] = True
            
            while i < n:
                values[i] = (not values[i-1])
                i += 1
                if not values[i-1-m]:
                    values[i] = (not values[i-2])
                    i, m = i+1, m+1
    
            return values[:n].count(True)
    

Log in to reply
 

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