LeetCode 38：外觀數列——字符串模擬生成第 n 項

題目描述

外觀數列：1, 11, 21, 1211, 111221, ...。第 n 項由讀出第 n-1 項得到（如 21 讀作「一個 2，一個 1」→ 1211）。求第 n 項字符串。

模擬算法

從 "1" 開始迭代 n-1 次。每次掃描當前字符串，統計連續相同字符個數，寫入 count + char 到新字符串。使用 stringstream 或 string 拼接。

C++ 實現

class Solution {
public:
    string countAndSay(int n) {
        string cur = "1";
        while (--n) {
            string nxt;
            int cnt = 1;
            for (int i = 1; i <= cur.size(); ++i) {
                if (i < cur.size() && cur[i] == cur[i-1]) ++cnt;
                else {
                    nxt += to_string(cnt);
                    nxt += cur[i-1];
                    cnt = 1;
                }
            }
            cur.swap(nxt);
        }
        return cur;
    }
};

關鍵點

• 循環條件 i <= cur.size() 統一處理最後一組字符。
• 字符串拼接用 += 或 stringstream 均可，現代編譯器優化下 string 足夠高效。

複雜度

• 時間：O(L_n)，L_n 為第 n 項長度（指數增長，n=30 時長度約 44 萬）。
• 空間：O(L_n)。

總結

外觀數列是字符串模擬的經典入門題。掌握「連續分組計數 → 輸出計數與字符」的模板，可應用於游程編碼、字符串壓縮等場景。