## [Leetcode]38. Count and Say(C++)

### 题目描述

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`，重复进如下一循环

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