Count and Say

Question

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.

Thoughts

其实就是找到如何处理这种字符串的规律，然后转换n-1次

Solution

class Solution:
    # @param {int} n the nth
    # @return {string} the nth sequence
    def countAndSay(self, n):
        # Write your code here
        result = "1"
        if not n or n == 1:
            return result
        #notice that it should be n-1, 1 is already 1 trans
        for i in range(n-1):
            result = self.getNextSeq(result)

        return result

    def getNextSeq(self, seq):
        length = len(seq)
        prefix = 1
        nextSeq = ""
        for j in range(length):
            if j == 0:
                cur = seq[j]
            else:
                if seq[j] == seq[j-1]:
                    prefix += 1
                else:
                    nextSeq += str(prefix) + str(cur)
                    prefix = 1
                    cur = seq[j]
        #add last sub sequence
        nextSeq += str(prefix) + str(cur)
        return nextSeq