Python Solution


  • 0
    T

    class Solution(object):
    def countAndSay(self, n):
    """
    :type n: int
    :rtype: str
    """

        def get_next_chunk(str_k, i):
            """
            given the value val at str_k[i], return the index j such that str_k[i], str_k[i] + 1, ..., str_k[j] are all equal
            """
            if i < len(str_k):
                val = str_k[i]
                j = i + 1
                while j < len(str_k) and str_k[j] == val:
                    j += 1
                return j, val
            else:  # in this case, the end of the last chunk was the last integer in the item. None, None means there are no more chunks in this item.
                return None, None
        
    
        k = 1
        cur = "1"  # item for n = 1
        next = ""  # holds the next item in sequence
        
        while k < n: # keep generating the next item in sequence up to n
            i = 0  # begin index of first chunk (sequence of identical integers)
            j, val = get_next_chunk(cur, i)  # get end index of first chunk, and the integer value for the chunk
            while j:  # keep getting the next chunk and appending integers to the next item in the sequence. stop when j is None
                next += str(j - i) + str(val)
                i = j
                j, val = get_next_chunk(cur, i)
            
            # Reset variables and increment k
            cur = next
            next = ""
            k += 1
            
        return cur

Log in to reply
 

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