Accepted python solution: not efficiency but easy to read


  • 4
    Q
    class Solution:
    # @return a string
    def countAndSay(self, n):
        s = ['1']
        result = '1'
        # The n-th sequance, input 1 should output '1'
        for i in range(n-1):
            start = 0
            temp = []
            # Process one sequence, scan from start to end
            while start < len(s):
                count = 1
                next = start + 1
                # Scan until s[next] is different
                while next < len(s) and s[start] == s[next]:
                    next += 1
                    count += 1
                # Get the new items in
                temp.append(str(count))
                temp.append(s[start])
                # Start from next one
                start = next
            # Concatenate list into string, using "," as separator in default 
            result = ''.join(temp)
            s = temp
        return result

  • 2
    R

    You don't need to convert the string into a list and convert it back. Can just use strings. :-D

    '1' + '1' = '11'


  • 0
    A

    @qjunchen What is the running time for this solution?


  • 0
    J

    @rj_flood yes but string addition is O(n) as strings are non mutable appending to list is O(1).


Log in to reply
 

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