Count and Say

题目描述

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

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

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

解题方法

找出生成这种string的规律，其实就是计数，如果当前的charcter等于之前的，就加1；否则就将现在的加到结果里，重新从1开始计数

Solution

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        # init string
        result = "1"
        if not n or n == 1:
            return result

        for i in range(n-1):
            result = self.getNext(result)

        return result

    def getNext(self, result):
        prefix = 1
        nextStr = ""
        length = len(result)
        for i in range(1, length):
            if result[i] == result[i-1]:
                prefix += 1
            else:
                nextStr += str(prefix) + result[i-1]
                prefix = 1
        nextStr += str(prefix) + result[-1]
        return nextStr

Reference