LeetCode 38. Count and Say 詳解

題目：外觀數列從 "1" 開始，每一項描述前一項的連續數字個數與值。前幾項：

1.     "1"
2.     "11"        (一個 1)
3.     "21"        (兩個 1)
4.     "1211"      (一個 2，一個 1)
5.     "111221"    (一個 1，一個 2，兩個 1)
...

給定 n (1 ≤ n ≤ 30)，返回第 n 項字符串。

核心邏輯：字符串「讀法」轉換

對字符串 s，從左到右掃描，統計連續相同字符的個數 cnt，輸出 to_string(cnt) + char。這是一個純字符串處理過程，無數學運算。

迭代實現 (C++ / Python / Java)

// C++
class Solution {
public:
    string countAndSay(int n) {
        string cur = "1";
        for (int i = 2; i <= n; ++i) {
            string nxt;
            for (int j = 0; j < cur.size(); ) {
                int k = j;
                while (k < cur.size() && cur[k] == cur[j]) ++k;
                nxt += to_string(k - j);
                nxt += cur[j];
                j = k;
            }
            cur = move(nxt);
        }
        return cur;
    }
};

# Python
class Solution:
    def countAndSay(self, n: int) -> str:
        cur = "1"
        for _ in range(n - 1):
            nxt = []
            i = 0
            while i < len(cur):
                j = i
                while j < len(cur) and cur[j] == cur[i]:
                    j += 1
                nxt.append(str(j - i))
                nxt.append(cur[i])
                i = j
            cur = "".join(nxt)
        return cur

// Java
class Solution {
    public String countAndSay(int n) {
        String cur = "1";
        for (int i = 2; i <= n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < cur.length(); ) {
                int k = j;
                while (k < cur.length() && cur.charAt(k) == cur.charAt(j)) k++;
                sb.append(k - j).append(cur.charAt(j));
                j = k;
            }
            cur = sb.toString();
        }
        return cur;
    }
}

關鍵觀察與優化

• 長度增長：數列長度近似指數增長（康威常數 ≈ 1.30357），n=30 時長度約 44 萬，仍在記憶體限制內。
• 只包含 1,2,3：經證明，外觀數列中永不出現大於 3 的數字（因為不可能有 4 個連續相同字符產生）。
• 無需遞歸：迭代更簡潔，避免棧溢出與重複計算。
• StringBuilder / list + join：避免字符串頻繁拷貝，提升效能。

複雜度分析

面試延伸

1. 逆向問題：給定某項，能否反推上一項？通常不可唯一確定（如 "11" 可能來自 "1" 或 "11" 的某種讀法）。
2. 變體：Count and Say II：允許數字超過 9，需用分隔符或定長編碼。
3. 康威常數：探討數列長度增長率的數學本質，屬於組合數學範疇。

總結

Count and Say 考察的是「字符串模式識別與生成」的基本功。關鍵在於正確實現「讀字符串寫計數」的邏輯，並善用 StringBuilder 類工具優化效能。這類題目在面試中常作為熱身題，代碼簡潔、邏輯清晰、邊界少，是展示編碼基本功的絕佳機會。