LeetCode 38 Count and Say：遞歸生成外觀數列

題目簡介

「外觀數列」：第 1 項 "1"。第 n 項由讀出第 n-1 項得到：連續相同數字計數後說出。如 "1"→"11"（一個1），"11"→"21"（兩個1），"21"→"1211"（一個2一個1）。求第 n 項字符串。

解題思路

遞歸生成：countAndSay(n) 調用 countAndSay(n-1) 得到上一項字符串，然後掃描統計連續相同字符，構建新字符串。在字符串末尾加哨兵字符簡化邊界處理。

代碼實現

public String countAndSay(int n) {
    if (n == 1) return "1";
    String prev = countAndSay(n-1) + "*"; // 哨兵
    StringBuilder sb = new StringBuilder();
    int cnt = 1;
    for (int i = 0; i < prev.length()-1; i++) {
        if (prev.charAt(i) == prev.charAt(i+1)) cnt++;
        else { sb.append(cnt).append(prev.charAt(i)); cnt = 1; }
    }
    return sb.toString();
}

複雜度分析

字符串長度約呈指數增長（康威常數 ≈1.303），n≤30 時極快。時間 O(L_n)，空間 O(L_n)。