力扣(LeetCode)38. 外观数列(C++)

双指针+模拟

初始字符串 $s$ 已给定，根据 $s$ 构造下一个外观数列 $t$ ，构造完毕， $s=t$ ，循环 $n-1$ 次，构造出一个外观数列。

构造步骤 :
令 $j$ 指向当前元素 ， $k$ 从 $j$ 往右，记录 $s[j]$ 出现的次数，当 $s[k]$ 不等于 $s[j]$ ，将 $k$ 记录的 $s[j]$ 的次数加入临时串 $t$ ，令 $j=k$ ，此时 $s[j]$ 指向下一个不同元素，循环上述操作。

class Solution {
public:
    string countAndSay(int n) {
        string s = "1";
        for(int i = 0;i<n-1;i++){
            string t;
            for(int j = 0;j<s.size();){
                int k = j + 1;
                while(k<s.size()&&s[k]==s[j]) k ++;
                t += to_string(k-j) + s[j];
                j = k;
            }
            s = t;
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1. 时间复杂度 : $O(n\times M)$ ， $n$ 已给定， $M$ 是构造的最长子串 ， 最坏时间复杂度 $O(n\times M)$ 。
2. 空间复杂度 : $O(M)$ ， $s$ 的最大长度是 $M$ ，对应空间复杂度 $O(M)$ 。

致语

理解思路很重要！
欢迎读者在评论区留言，答主看到就会回复的。

AC