題目資訊

• 題目編號: 2900
• 題目連結: Longest Unequal Adjacent Groups Subsequence I
• 主題: Array, String, Dynamic Programming, Greedy

題目敘述

你有一個字串陣列 words 和一個二元陣列 groups，兩者長度皆為 $n$，其中 $words[i]$ 與 $groups[i]$ 相關聯。

你的任務是從 words 中選擇最長的交錯子序列。words 的一個子序列是交錯的，若在該序列中任意相鄰兩個字串在二元陣列 groups 中對應的元素不同。基本上，你需要選擇字串使得相鄰元素在 groups 陣列中對應的位不相匹。

正式來說，你需要找到一個長度為 $[0, 1, \ldots, n - 1]$ 的索引陣列的最長子序列，記為 $[i_0, i_1, \ldots, i_{k-1}]$，滿足對每個 $0 \leq j < k - 1$，$groups[i_j] \neq groups[i_{j+1}]$，然後找出這些索引對應的字。

返回被選擇的子序列。如果有多個答案，返回任一即可。

注意： words 中的元素是不同的。

範例 1:

輸入: words = ["e","a","b"], groups = [0,0,1]

輸出: ["e","b"]

解釋: 可以選擇的子序列為 ["e","b"] 因為 $groups[0] \neq groups[2]$。另一個可以選擇的子序列是 ["a","b"] 因為 $groups[1] \neq groups[2]$。可以證明，滿足條件的最長索引子序列的長度是 $2$。

範例 2:

輸入: words = ["a","b","c","d"], groups = [1,0,1,1]

輸出: ["a","b","c"]

解釋: 可以選擇的子序列為 ["a","b","c"] 因為 $groups[0] \neq groups[1]$ 且 $groups[1] \neq groups[2]$。另一個可以選擇的子序列是 ["a","b","d"] 因為 $groups[0] \neq groups[1]$ 且 $groups[1] \neq groups[3]$。可以證明，滿足條件的最長索引子序列的長度是 $3$。

限制條件:

• $1 \leq n == words.length == groups.length \leq 100$
• $1 \leq words[i].length \leq 10$
• $groups[i]$ 是 $0$ 或 $1$。
• words 由不同的字串組成。
• $words[i]$ 由小寫英文字母組成。

直覺

此題要求我們從一組單詞的列表中找到最長的交替子序列，這是由一個二進制數組所決定的，該數組指示每個單詞的“組別”。主要目標是選擇單詞，使得任何連續的選擇單詞組別不同。這種交替模式對於子序列來說至關重要。有鑑於此，我們的方法將利用這些限制：確保子序列中每個連續對的組別值不同，以最大化該子序列的長度。

解法

解決方案逐一檢查給定數組中每個單詞及其相關的組別值。過程從包含第一個單詞開始，自然而然地確立子序列的起點。隨著在單詞列表中的進展，它將當前單詞的組別值與之前選擇的單詞的組別值進行比較：

1. 初始設置：我們首先建立一個結果列表，其中最初包含第一個單詞，因為這設置了子序列的基本元素。

2. 迭代評估：

   • 從第二個元素開始迭代 words 數組。
   • 對於每個單詞，檢查其對應的組別（來自 groups 數組）是否與結果子序列中先前包含的單詞的組別不同。
   • 若組別不同，則將當前單詞附加到我們的結果列表中，從而延長子序列。
   • 更新最近遇到的組別記錄，以反映新添加單詞的組別。

3. 結果彙編：當單詞的迭代完成後，結果列表將包含滿足交替組別條件的最長可能子序列。

該演算法對單詞數量是線性操作的，只需要對每個單詞檢查一次，並基於即時比較來做出每個決策。這種直截了當的貪婪方法通過抓住每個符合條件的機會來擴展序列，有效地構建了最長的交替子序列。

程式碼

C++

class Solution {
public:
    vector<string> getLongestSubsequence(vector<string>& words, vector<int>& groups) {
        int len = words.size();  //  words 陣列的長度
        int last_group = groups[0];  //  初始化最後的組別狀態為第一個元素的組別
        vector<string> result = {words[0]};  //  從第一個字開始結果

        for (int i = 1; i < len; ++i) {
            //  檢查當前的組是否與最後的組別不同
            if (groups[i] != last_group) {
                result.emplace_back(words[i]);  //  如果有交替，將該字加入結果
                last_group = groups[i];  //  更新最後的組別狀態
            }
        }
        return result;  //  返回最長的交替子序列
    }
};

Python

class Solution:
    def getLongestSubsequence(self, words: list[str], groups: list[int]) -> list[str]:
        len_ = len(words)  # words陣列的長度
        last_group = groups[0]  # 用第一個元素的群組初始化最後的群組狀態
        result = [words[0]]  # 用第一個單詞開始結果

        for i in range(1, len_):
            # 檢查當前群組是否與上一個群組不同
            if groups[i] != last_group:
                result.append(words[i])  # 如果交替則將單詞加入結果
                last_group = groups[i]  # 更新最後的群組狀態
        
        return result  # 返回最長的交替子序列

複雜度分析

• 時間複雜度: $O(n)$
  該演算法在單次遍歷中對輸入數組 words 和 groups 的每個元素進行處理，因此時間複雜度為 $O(n)$，其中 $n$ 表示數組中的元素數量。對於每個元素，演算法會檢查一個簡單的條件，並有可能將一個單詞附加到結果數組中。
• 空間複雜度: $O(n)$
  空間複雜度為 $O(n)$ 是由於存儲結果數組所需的空間。在最壞的情況下，結果數組可能包含最多 $n$ 個元素，因為每個單詞都有可能成為交替子序列的一部分。輔助變量和輸入參數所使用的空間相比之下是可以忽略不計的。