題目資訊

題目編號: 1415
題目連結: The k-th Lexicographical String of All Happy Strings of Length n
主題: String, Backtracking

題目敘述

一個快樂字串是一個滿足以下條件的字串：

僅由集合 $[‘a’, ‘b’, ‘c’]$ 中的字母組成。
對於從 $1$ 到 $s.length - 1$ 的所有 $i$ 值，滿足 $s[i] \neq s[i + 1]$ （字串是從1開始計數）。

例如，字串 “abc”、“ac”、“b” 和 “abcbabcbcb” 都是快樂字串，而字串 “aa”、“baa” 和 “ababbc” 則不是快樂字串。

給定兩個整數 $n$ 和 $k$，考慮所有長度為 $n$ 的快樂字串的列表，並按字典順序排序。

返回該列表的第 kth 個字串，如果長度為 $n$ 的快樂字串少於 $k$ 個，則返回一個空字串。

範例 1:

輸入: n = 1, k = 3
輸出: "c"
解釋: 列表 ["a", "b", "c"] 包含所有長度為 1 的快樂字串。第三個字串是 "c"。

範例 2:

輸入: n = 1, k = 4
輸出: ""
解釋: 僅有 3 個長度為 1 的快樂字串。

範例 3:

輸入: n = 3, k = 9
輸出: "cab"
解釋: 有 12 個不同的長度為 3 的快樂字串 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]。你會找到第 9 個字串 = "cab"

限制條件:

$1 \leq n \leq 10$
$1 \leq k \leq 100$

直覺

這個問題實際上可以通過模擬三進位數來解決。由於我們只能使用 ‘a’、‘b’ 和 ‘c’ 三個字符，且相鄰字符不能相同，所以本質上是在生成一個特殊的三進位序列。我們可以將 ‘a’、‘b’ 和 ‘c’ 視為 0、1 和 2，並通過模擬進位的方式來生成所有可能的快樂字串。通過使用一個額外的前導位置（即 n+1 長度的陣列）來簡化進位操作，我們可以更容易地處理邊界情況。

解法

初始化：
- 創建一個長度為 n+1 的陣列，全部初始化為 ‘a’。
- 第一個位置（索引 0）作為進位指示器，不是實際字串的一部分。
特殊情況處理：
- 當 n = 1 時，由於初始的 ‘a’ 已為快樂字串，因此將 k 減 1。
三進位模擬：
- 使用最後一個字符作為最低位，進行遞增操作。
- 當字符超過 ‘c’ 時，將其重置為 ‘a’ 並向前進位。
- 如果進位到第一個位置（索引 0）且超過 ‘a’，表示已經生成所有可能的快樂字串。
快樂字串驗證：
- 檢查相鄰字符是否相同。
- 只有當整個字串都符合條件時才計數（k 減 1）。
結果獲取：
- 當找到第 k 個有效的快樂字串時（k = 0），返回結果。
- 如果無法找到第 k 個快樂字串（首位超過 ‘a’），返回空字串。

程式碼

C++

class Solution {
public:
    string getHappyString(int n, int k) {
        // 建立一個大小為 n+1 的向量，初始化為 'a'，用來儲存當前的歡樂字串。
        vector<char> currentString(n + 1, 'a');
        
        // 當 n == 1 時，只有 "a", "b", "c" 這三種可能的歡樂字串。
        // 我們將 k 減去 1 以符合 0 基礎索引。
        if (n == 1) k--;

        // 迴圈執行直到找到第 k 個歡樂字串。
        while (k > 0) {
            // 增加字串的最後一個字元。
            currentString[n]++;
            
            // 從尾部開始檢查是否有任何字元超過 'c' 並重設為 'a'。
            // 增加前一個字元。
            int i;
            for (i = n; currentString[i] > 'c'; i--) {
                currentString[i] = 'a';
                currentString[i - 1]++;
            }
            
            // 如果第一個字元超過 'c'，則不可能有第 k 個歡樂字串。
            if (currentString[0] != 'a') return "";

            // 檢查字串是否為歡樂字串，確保沒有兩個連續的字元相同。
            for (i = 1; i < n; i++) {
                if (currentString[i] == currentString[i + 1]) break;
            }

            // 如果找到有效的歡樂字串，則減少 k。
            if (i == n) k--;
        }
        
        // 返回第 k 個歡樂字串，排除第一個佔位字元。
        return string(currentString.begin() + 1, currentString.end());
    }
};

Python

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        # 建立一個大小為 n+1 的列表以 'a' 初始化，用於儲存當前的快樂字串。
        currentString = ['a'] * (n + 1)
        
        # 當 n == 1 時，只有三種可能的快樂字串: "a", "b", "c"。
        # 將 k 減去 1 以符合 0 基底的索引。
        if n == 1:
            k -= 1

        # 迴圈直到找到第 k 個快樂字串。
        while k > 0:
            # 將字串的最後一個字元遞增。
            currentString[n] = chr(ord(currentString[n]) + 1)
            
            # 從結尾檢查是否有字元超過 'c' 並將其重設為 'a'。
            # 將前一個字元遞增。
            i = n
            while currentString[i] > 'c':
                currentString[i] = 'a'
                currentString[i - 1] = chr(ord(currentString[i - 1]) + 1)
                i -= 1
            
            # 如果第一個字元超過 'c'，則不可能存在第 k 個快樂字串。
            if currentString[0] != 'a':
                return ""

            # 檢查字串是否為快樂字串，確保沒有兩個連續的字元相同。
            for i in range(1, n):
                if currentString[i] == currentString[i + 1]:
                    break

            # 如果找到有效的快樂字串，遞減 k。
            if i == n:
                k -= 1
        
        # 返回第 k 個快樂字串，排除第一個佔位字元。
        return ''.join(currentString[1:])

複雜度分析

時間複雜度: $O(3^n)$
該演算法通過考慮集合 $[‘a’, ‘b’, ‘c’]$ 中的每一個字符來生成所有長度為 $n$ 的快樂字符串。在最壞的情況下，對於字符串的每一個位置 $n$，最多有 3 種選擇，即總共有 $3^n$ 種可能的字符串。演算法中的迴圈相較於這些字符串的生成不會單獨增加額外的複雜度。因此，時間複雜度由需要檢查的指數數量的字符串決定。
空間複雜度: $O(n)$
空間複雜度主要由存儲當前正在構建的快樂字符串的向量 currentString 決定。由於該向量的大小為 $n+1$，因此貢獻了一個 $O(n)$ 的空間複雜度。其他空間需求，如迴圈變量或函數調用堆疊，不超過此線性空間需求。

CS Note
En

Leetcode 1415. The k-th Lexicographical String of All Happy Strings of Length n

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析