0%

### 题目描述

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 integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.

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

### 例子

#### 例子 1

Input: 1
Output: “1”
Explanation: This is the base case.

#### 例子 2

Input: 4
Output: “1211”
Explanation: For n = 3 the term was “21” in which we have two groups “2” and “1”, “2” can be read as “12” which means frequency = 1 and value = 2, the same way “1” is read as “11”, so the answer is the concatenation of “12” and “11” which is “1211”.

### 解题思路

• `n = 1` 时，返回 `"1"`
• `n > 1` 时，进入循环过程，对每一次循环从前往后遍历上一个字符串(`current`)并统计连续相同的字符按题目要求（次数 + 对于字符）加至新字符串(`next`)中，遍历一遍旧字符串后（这里注意要将末尾剩余的一部分也加至 `next` 中）将 `current` 赋值为 `next`，重复进如下一循环

• 时间复杂度: O(n * k) k 为最长字符串长度
• 空间复杂度: O(k) k 为最长字符串长度

GitHub 代码同步地址： 38.CountAndSay.cpp

GitHub: Leetcode-C++-Solution