題目資訊

• 題目編號: 38
• 題目連結: Count and Say
• 主題: String

題目敘述

The 數數並說 序列是一個由遞迴公式定義的數字字符串序列：

• countAndSay(1) = "1"
• countAndSay(n) 是 countAndSay(n - 1) 的運行長度編碼。

運行長度編碼（RLE）是一種字符串壓縮方法，通過用字符和標記字符計數（運行長度）的數字連接來替換連續相同的字符（重複2次或更多次）來實現。例如，要壓縮字符串 "3322251"，我們將 "33" 替換為 "23"，將 "222" 替換為 "32"，將 "5" 替換為 "15"，並將 "1" 替換為 "11"。因此，壓縮後的字符串變為 "23321511"。

給定一個正整數 n，返回 數數並說 序列的第 $n^{th}$ 個元素。

範例 1:

輸入： $n = 4$

輸出： "1211"

解釋：

countAndSay(1) = "1"
countAndSay(2) = "1" 的運行長度編碼 = "11"
countAndSay(3) = "11" 的運行長度編碼 = "21"
countAndSay(4) = "21" 的運行長度編碼 = "1211"

範例 2:

輸入： $n = 1$

輸出： "1"

解釋：

這是基本情況。

約束條件：

• $1 \leq n \leq 30$

進一步探索: 你能迭代地解決它嗎？

直覺

「讀數說數」序列是一種有趣的應用，其核心在於運用游程編碼技術，每一項的生成是透過對前一項進行編碼來實現的。目標在於依據前一項中的連續數字數目，轉換並生成一個描述各數字出現次數的字串。這需要理解序列中從一項轉換到下一項的模式，其性質是遞迴定義的序列。

解法

解決此問題的方法涉及使用一個遞迴函數 countAndSay，根據「讀數說數」規則生成字串序列。遞迴的基本情況相當直接：當 $n=1$ 時，唯一的序列元素是字串 "1"。對於後續的值，我們利用遞迴得出第 $(n-1)$ 項。

1. 基本情況：如果 $n=1$，返回字串 "1"。

2. 遞迴調用：對於其他情況，進行遞迴呼叫 countAndSay(n-1) 以獲取前一項序列。

3. 游程編碼：

   • 一旦獲得第 $(n-1)$ 項，我們需要對其進行編碼以形成第 $n$ 項。
   • 遍歷第 $(n-1)$ 項的字元，並記錄連續相同字元的數量。
   • 對於每一組不同的連續字元，將其數量和字元附加到新的字串（currentTerm）上。

4. 遍歷字元：

   • 對第一個字元初始化一個計數器 count 為 1。
   • 使用索引遍歷字串。將每個字元與下一個字元比較。
   • 若相同則遞增計數器，若不同則將計數器和字元附加到 currentTerm，重置計數器，繼續處理下一個不同的字元。

5. 返回結果：迴圈結束後，currentTerm 將包含編碼完成的字串，即序列的第 $n$ 項。這即為結果返回。

透過此遞迴與編碼的過程，序列中的每個元素都根據前一元素的描述生成，正式捕捉了「讀數說數」方法的本質。

程式碼

C++

class Solution {
public:
    // 函數用於生成"數數說"序列的第 n 項
    string countAndSay(int n) {
        // 基本情況：第一項是 "1"
        if (n == 1) return "1";
        
        // 遞迴生成第 (n-1) 項
        string previousTerm = countAndSay(n - 1);
        string currentTerm = "";
        
        // 遍歷第 (n-1) 項以對其進行編碼
        for (int i = 0; i < previousTerm.size(); i++) {
            int count = 1;
            // 計算連續相同字元的數量
            while (i + 1 < previousTerm.size() && previousTerm[i] == previousTerm[i + 1]) {
                count++;
                i++;
            }
            // 將數量和字元附加到結果字串
            currentTerm += to_string(count) + previousTerm[i];
        }
        
        return currentTerm;
    }
};

Python

class Solution:
    # 生成第 n 項 count-and-say 序列的函數
    def countAndSay(self, n: int) -> str:
        # 基本情況：第一項是 "1"
        if n == 1:
            return "1"
        
        # 遞迴生成第 (n-1) 項
        previousTerm = self.countAndSay(n - 1)
        currentTerm = ""
        
        # 遍歷第 (n-1) 項以進行編碼
        i = 0
        while i < len(previousTerm):
            count = 1
            # 計算連續相同字符的數量
            while i + 1 < len(previousTerm) and previousTerm[i] == previousTerm[i + 1]:
                count += 1
                i += 1
            # 將計數和字符附加到結果字串
            currentTerm += str(count) + previousTerm[i]
            i += 1
        
        return currentTerm

複雜度分析

• 時間複雜度: $O(2^n)$。這是因為每次調用 countAndSay 都需要處理前一項的所有字符。序列的長度在每一步中大約會加倍，導致指數增長。因此，處理需要 $O(2^{n-1}) + O(2^{n-2}) + \ldots + O(1)$，其總和為 $O(2^n)$。
• 空間複雜度: $O(2^n)$。這考慮了存儲函數結果所需的空間，以及由於遞歸導致的堆疊空間。與時間複雜度類似，由於每個後續序列的大小大約可以加倍，因此空間需求會指數增長，導致空間需求為 $O(2^n)$。