# 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
```

`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 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://rachel2011.gitbook.io/leetcode_cc150/leetcode/count-and-say.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.