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"or11. 11is read off as"two 1s"or21. 21is read off as"one 2, thenone 1"or1211.

Given an integern, generate thenthterm 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"

题意：

n = 1时，打印一个1。

n = 2时，看n=1那一行，念：1个1，所以打印：11。

n = 3时，看n=2那一行，念：2个1，所以打印：21。

n = 4时，看n=3那一行，念：一个2一个1，所以打印：1211。

思路：

逐个构建序列——根据第i-1个序列构建后第i个。理解题目意思后便知道在扫描前一个序列ret时，需要一个计数变量count记录当前字符重复的次数，以及需要一个字符变量prev记录上一个字符的值。当ret[i] = prev，则先不写入结果，而增加count。当ret[i] != prev时，说明prev的重复结束，需要将count和prev都写入结果，然后重置count为1，prev为ret[i]。

注意：跑完循环之后记得把最后一个字符也加上，因为之前只是计数而已

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        result = '1'

        for i in xrange(2, n+1):
            prev = result[0]
            temp = ''
            count = 1
            for j in xrange(1, len(result)):
                if result[j] == prev:
                    count += 1
                else:
                    temp += str(count) + prev
                    prev = result[j]
                    count = 1
            temp += str(count) + prev
            result = temp
        return result

In Python its more efficient to use ''.join() to concatenate strings. So it will be faster to use a list to store the substrings and join them at the end.

Every time you concatenate two strings with the plus operator, the Python’s interpreter allocates some memory and copies the two strings into it, one after the other. When using the join method, Python allocates memory for the joined string only once.

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        result = '1'

        for i in xrange(2, n+1):
            prev = result[0]
            temp = []
            count = 1
            for j in xrange(1, len(result)):
                if result[j] == prev:
                    count += 1
                else:
                    temp.append(str(count))
                    temp.append(prev)
                    prev = result[j]
                    count = 1
            temp.append(str(count))
            temp.append(prev)
            result = ''.join(temp)
        return result