Straightforward O(n) solution in python with detailed explaination


  • 0
    L

    Lets start by example:

    S = '1 22 11 2' 
    S' = '1 2 2 1'
    

    Based on the description we can easily get the next num of S' should be 1 since S' is exactly the substring of S, so the question would become how to compose the next part of S?

    The '1' means either 1 or 2 for the next part of S, and the answer must be 1 because if it was 2, then S = '1 22 11 22' and S' would be 1 2 2 2. That's wrong.

    So we come up with the conclusion that The next part of S is based on the last num of current S. below is my solution, beat more than 90% python code:

    class Solution(object):
        def magicalString(self, n):
            """
            :type n: int
            :rtype: int
            """
            s, last_s = '122', '2' #initial value, defined formula
            ml = 2  #The cout of S'
            old = n # Original n
            while n > 3:
                next_num = s[ml]
                if next_num == '2':
                    if last_s == '2':
                        s += '11'
                        last_s = '1'
                    else:
                        s += '22'
                        last_s = '2'
                    n -=2
                    
                if next_num == '1':
                    if last_s == '1':
                        s += '2'
                        last_s = '2'
                    else:
                        s += '1'
                        last_s = '1'
                    n -= 1
                ml += 1
            return s[:old].count('1')
    

    Yes, the code may not neat, but how many of you would come up with neat solution on the short interview:)


Log in to reply
 

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