38. Count and Say

问题

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 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, generate the nth sequence.

例子

5
111221

分析

统计字符串的连续重复字符

要点

尽量迭代，不用递归

时间复杂度

O(n^2) n次迭代，每次迭代的结果字符串的长度呈线性增长。

空间复杂度

O(1)

代码

class Solution {
public:
    string countAndSay(int n) {
        string res("1");
        for (int i = 0; i < n - 1; i++)
            res = say(res);
        return res;
    }
    
private:
    string say(const string &str) {
        string res;
        char c = str[0];
        int cnt = 1;
        for (int i = 1; i < str.size(); i++) {
            if (str[i] == c) cnt++;
            else {
                res += to_string(cnt) + string(1, c);
                c = str[i];
                cnt = 1;
            }
        }
        res += to_string(cnt) + string(1, c);
        return res;
    }
};