runtime 0 ms, beats 100% of cpp submissions
O(4^(n/3)) solution with explanation

tags: simulation

Count and Say

📖 description

給定一個數字，以固定型式生成字串。

ex.
    Input: n = 4
    Output: "1211"
    
    Explanation:
    countAndSay(1) = "1"
    countAndSay(2) = say "1" = one 1 = "11"
    countAndSay(3) = say "11" = two 1's = "21"
    countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

🧠 solution

根據需求模擬字串生成。

紀錄當前數字出現了幾次，當遇到下一個不同的數字，字串 += 次數， += 數字，並重製當前狀態，看新的數字。

⏳ time complexity

solution
總時間複雜度 O(4^(n/3))

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string gen(string str){
        string str1;
        int m=str.size();
        char c=str[0];
        int cnt=1;
        for(int i=1;i<m;i++){
            if(c!=str[i]){
                str1+=(cnt+'0');    // 累加次數
                str1+=c;            // 累加數字
                c=str[i];           // 更新狀態
                cnt=1;
            }
            else{
                cnt++;
            }
        }
        str1+=(cnt+'0');
        str1+=c;
        return str1;
    }
    string countAndSay(int n) {
        string str="1";
        for(int i=2;i<=n;i++){
            str=gen(str);   // 遞迴更新字串
        }
        return str;
    }
};