38 外观数列

https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnpvdm/

https://leetcode.cn/problems/count-and-say/description/

cost: 9m3s

class Solution {
public:
    string countAndSay(int n) {
        vector<string> memo(n + 1);
        memo[1] = "1";
        for (int i = 2; i <= n; i++) {
            int cnt = 0;
            char lastChar = 0;
            for (const char ch : memo[i - 1]) {
                if (ch != lastChar && cnt != 0) {
                    memo[i] += std::to_string(cnt) + lastChar;
                    cnt = 0;
                }
                lastChar = ch;
                cnt++;
            }
            if (cnt > 0) {
                memo[i] += std::to_string(cnt) + lastChar;
            }
        }
        return memo[n];
    }
};

• 时间复杂度：O(N * M), M 为生成的字符串中的最大长度
• 空间复杂度：O(M)