LeetCode Count and Say（外觀數列）

一、題目描述

「外觀數列」是一個整數序列，從 "1" 開始，每一項都是對前一項的描述：

• 1 被讀作 "one 1" → "11"
• 11 被讀作 "two 1s" → "21"
• 21 被讀作 "one 2, one 1" → "1211"
• 1211 被讀作 "one 1, one 2, two 1s" → "111221"

給定正整數 n，返回第 n 項。注意：所有項均以字符串形式表示。

二、解題思路：模擬生成

從 "1" 開始，迭代 n-1 次。每次生成下一項：遍歷當前字符串，統計連續相同字符的個數，拼接「個數+字符」。

三、代碼實現（Python）

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        result = "1"
        for _ in range(1, n):
            result = self.getNext(result)
        return result

    def getNext(self, s):
        result = []
        start = 0
        while start < len(s):
            curr = start + 1
            while curr < len(s) and s[start] == s[curr]:
                curr += 1
            # 連續個數 = curr - start
            result.append(str(curr - start))
            result.append(s[start])
            start = curr
        return "".join(result)

# 測試
if __name__ == "__main__":
    assert Solution().countAndSay(4) == "1211"
    assert Solution().countAndSay(5) == "111221"

四、複雜度分析

• 時間複雜度：O(2^n) 近似，字符串長度指數增長
• 空間複雜度：O(2^n) 存儲中間字符串

本題考察字符串處理與模擬能力，代碼簡潔直觀。