### 题目描述

题目链接：38. 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 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: 1Output: “1”Explanation: This is the base case.

#### 例子 2

Input: 4Output: “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`

，重复进如下一循环

代码如下：

```
#include <string>
class Solution {
public:
std::string countAndSay(int n) {
std::string current = "1";
int step = 1;
while (step < n) {
step++;
std::string next = "";
int count = 1;
for (int i = 0; i < current.length() - 1; i++) {
if (current[i] == current[i + 1]) {
count++;
} else {
next += std::to_string(count) + current[i];
count = 1;
}
}
next += std::to_string(count) + current.back();
current = next;
}
return current;
}
};
```

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

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

其他题目： GitHub: Leetcode-C++-Solution 博客：Leetcode-Solutions