38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1is read off as"one 1"or 11.
11is read off as"two 1s"or21.
21is read off as"one 2, then one 1"or 1211.

Given an integer n where 1 ≤n≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

Thoughts:

  1. Two pointers: each time counting the number of continuous same number
class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n < 1: return '0'
        res = '1'
        for k in xrange(1,n):
            i, j, tmp = 0,0, ''
            while j < len(res):
                if res[i] == res[j]:
                    j +=1
                else:
                    tmp += str(j - i) + str(res[i])
                    i = j
            tmp += str(j - i) + str(res[i])
            res = tmp

        return res

results matching ""

    No results matching ""