[LeetCode解題攻略] 38. Count and Say

問題描述

Count-and-say序列是透過遞歸公式定義的數字串序列：

countAndSay(1) = "1"

Run-length encoding (RLE) 是一種字串壓縮方法，其工作原理是將連續相同的字元（重複 2 次或更多次）替換為字元和標記字元數（length of the run）的數字的連接。例如，為了壓縮字串“3322251”，我們用“23”替換“33”，用“32”替換“222”，用“15”替換“5”，用“11”替換“1”。因此壓縮後的字串變成「23321511」。

給定一個正整數 n，傳回count-and-say序列的第 n 個元素。

範例 1

輸入：n = 1
輸出："1"
解釋：第一項是 "1"。

範例 2

輸入：n = 4
輸出："1211"
解釋：
第 1 項是 "1"。
第 2 項是 "11"（1 個 1）。
第 3 項是 "21"（2 個 1）。
第 4 項是 "1211"（1 個 2，1 個 1）。

解題思路

該題的本質是一個遞推問題，從 n = 1 開始，不斷基於前一項生成新的數列。

• 關鍵點：
• 1. 如何描述一個數列？從左到右依次統計連續的相同數字出現的次數，然後生成描述字符串。
  2. 每一項都依賴於前一項，因此需要迭代生成。
• 解題策略：
• 1. 使用字符串保存當前數列的描述。
  2. 遍歷該字符串，統計每個數字連續出現的次數，然後生成新的字符串。
  3. 重複上述過程，直到生成第 n 項。

解法一：模擬法

思路

• 從第一項開始，依次生成每一項。
• 使用一個輔助函數來根據前一項生成當前項。

程式碼

class Solution:
    def countAndSay(self, n: int) -> str:
        def next_sequence(s):
            result = []
            count = 1
            for i in range(1, len(s)):
                if s[i] == s[i - 1]:
                    count += 1
                else:
                    result.append(str(count))
                    result.append(s[i - 1])
                    count = 1
            result.append(str(count))
            result.append(s[-1])
            return ''.join(result)

        sequence = "1"
        for _ in range(n - 1):
            sequence = next_sequence(sequence)
        return sequence

解釋

1. 輔助函數 next_sequence：
2. • 用於生成下一項數列。
   • 遍歷當前字符串，統計連續數字的次數，並將結果保存為新的字符串。
   • 時間複雜度為 O(k)，其中 k 是當前字符串的長度。
2. 主函數 countAndSay：
3. • 初始數列為 "1"。
   • 不斷調用 next_sequence，生成第 n 項。

時間與空間複雜度

• 時間複雜度：O(m)，其中 m 是所有數列總長度。
• • 每次生成的數列長度與前一項成線性增長，總計約為 O(2^n)。
• 空間複雜度：O(k)，其中 k 是當前字符串的長度。

解法二：遞歸法

思路

• 使用遞歸的方法生成第 n 項。
• 基於第 n-1 項，統計每個數字的出現次數，生成新的字符串。

程式碼

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        
        prev_sequence = self.countAndSay(n - 1)
        result = []
        count = 1

        for i in range(1, len(prev_sequence)):
            if prev_sequence[i] == prev_sequence[i - 1]:
                count += 1
            else:
                result.append(str(count))
                result.append(prev_sequence[i - 1])
                count = 1
        result.append(str(count))
        result.append(prev_sequence[-1])
        return ''.join(result)

解釋

1. 基底條件：
2. • 當 n = 1 時，返回 "1"。
2. 遞歸步驟：
3. • 基於第 n-1 項進行數字統計，生成當前項。

時間與空間複雜度

• 時間複雜度：O(m)，同樣為所有數列總長度。
• 空間複雜度：O(n)，因為遞歸需要額外的棧空間。

結論

• 解法一 模擬法通過迭代生成每一項，便於理解與實現。
• 解法二 遞歸法更加直觀，但需要注意遞歸深度的限制。
• 雖然該問題的本質是模擬與遞推，但隨著 n 增大，生成數列的時間與空間消耗將指數增長，因此需要合理處理大輸入的情況。