38.Count and Say

Tags: [implementation], [loop], [counter]

Com: {fb}

Link: https://leetcode.com/problems/count-and-say/#/description

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1is read off as"one 1"or11.
11is read off as"two 1s"or21.
21is read off as"one 2, then one 1"or1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

More clean solution:

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n <= 0:
            return ''

        result = '1'
        for _ in xrange(1, n):
            result = self.read(result)

        return result

    def read(self, s):
        if not s:
            return ''

        result = []
        index = 0
        counter = 0
        start = None

        while index < len(s):
            curr = s[index]
            if not start:
                start = curr
            elif start != curr:
                result.append(str(counter))
                result.append(start)
                start = curr
                counter = 0

            counter += 1
            index += 1

        result.append(str(counter))
        result.append(start)
        return ''.join(result)

Note:

• Time complexity = O(n^2), may not very tight.

Solution:

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n <= 0:
            return ''

        result = '1'
        for _ in xrange(1, n):
            result = self.read(result)

        return result

    def read(self, s):
        if not s:
            return ''

        result = []
        start = s[0]
        counter = 1
        index = 1
        while index < len(s):
            curr = s[index]
            if start != curr:
                result.append(str(counter))
                result.append(start)
                counter = 0
                start = curr

            counter += 1
            index += 1

        result.append(str(counter))
        result.append(start)

        return ''.join(result)

Note:

• Time complexity = O(n^2). The upper bound of time complexity is O(n^2), but this may not very tight.