題目資訊

題目編號: 2901
題目連結: Longest Unequal Adjacent Groups Subsequence II
主題: Array, String, Dynamic Programming

題目敘述

您得到一個字串陣列 words 和一個陣列 groups，兩個陣列的長度皆為 $n$。

兩個等長字串之間的漢明距離是它們對應字元不同的位置數量。

您需要從一個索引陣列 $[0, 1, …, n - 1]$ 中選擇最長的子序列，使得對於標記為 $[i_0, i_1, …, i_{k-1}]$ 且長度為 $k$ 的子序列，滿足下列條件:

對於子序列中相鄰的索引，它們對應的群組是不相等的，即 $groups[i_j] \neq groups[i_{j+1}]$，對於每個 $j$，其中 $0 < j + 1 < k$。
$words[i_j]$ 和 $words[i_{j+1}]$ 的長度相等，並且它們的漢明距離是 $1$，其中 $0 < j + 1 < k$，對於子序列中的所有索引。

返回包含在選定子序列中對應索引的字串陣列（按順序）。如果有多個答案，返回其中之一。

注意: words 中的字串可能不等長。

範例 1:

輸入: words = ["bab","dab","cab"], groups = [1,2,2]

輸出: ["bab","cab"]

解釋: 可以選擇的子序列是 [0,2]。

$groups[0] \neq groups[2]$
$words[0].length == words[2].length$，並且它們之間的漢明距離為 1。

所以，有效的答案是 [words[0],words[2]] = ["bab","cab"]。

另一個可以選擇的子序列是 [0,1]。

$groups[0] \neq groups[1]$
$words[0].length == words[1].length$，並且它們之間的漢明距離為 $1$。

所以，另一個有效的答案是 [words[0],words[1]] = ["bab","dab"]。

可以證明，滿足條件的最長的索引子序列的長度是 $2$。

範例 2:

輸入: words = ["a","b","c","d"], groups = [1,2,3,4]

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

解釋: 我們可以選擇子序列 [0,1,2,3]。

它滿足兩個條件。

因此，答案是 [words[0],words[1],words[2],words[3]] = ["a","b","c","d"]。

它在所有滿足條件的索引子序列中具有最長的長度。

因此，這是唯一的答案。

約束條件:

$1 \leq n == words.length == groups.length \leq 1000$
$1 \leq words[i].length \leq 10$
$1 \leq groups[i] \leq n$
words 由不同的字串組成。
$words[i]$ 由小寫英文字符組成。

直覺

本問題要求找到字串陣列中指數形成的子序列，使得該子序列中的每一對連續字串滿足兩個條件：每個字串屬於不同的群組，且字串之間的海明距離（Hamming distance）恰好為1。可以將每個字串視為圖中的一個節點，若兩個節點符合給定條件，則在它們之間存在一條邊。於是問題轉化為尋找此圖中的最長路徑。

解法

所採用的方法使用動態規劃技術，系統性地識別滿足條件的有效子序列。以下是該方法的詳細說明：

輔助函數 - hammingDistanceCheck:
定義一個輔助函數 hammingDistanceCheck 用來判定兩個字串的海明距離是否恰好為1。該函數會檢查兩個字串的長度是否相等，並對每對字符進行遍歷以計算不同之處。如果剛好有一處字符不同，則返回 true；否則返回 false。
初始化:
- 初始化一個動態規劃陣列 dp，其中每個元素 dp[i] 表示以索引 i 結尾的最長子序列的長度。最初將每個元素設為1，因為每個字串本身可被視為一個簡單的子序列。
- 使用一個陣列 ans 來追踪構成每個索引對應的子序列的字串。每個索引用該位置的字串初始化。
動態規劃轉移:
- 透過雙重迴圈遍歷字串陣列。對於每一個從1到 len-1 的 i 和每個從 i-1 到0的 j：
  - 檢查群組指數是否不同 (groups[i] != groups[j])。
  - 驗證將索引 i 處的當前字串添加到以 j 結尾的子序列能否增加子序列的長度 (dp[j] + 1 > dp[i])。
  - 使用 hammingDistanceCheck 函數確保索引 i 和 j 處的字串的海明距離恰好為1。
- 如果所有條件都滿足，則更新子序列長度和實際子序列：
  - 設定 dp[i] = dp[j] + 1。
  - 更新 ans[i] 為從 ans[j] 開始的子序列並添加 words[i]。
結果提取:
- 經過所有對的處理後，透過找到 dp 陣列中最大值的索引來確定最長子序列的索引。
- 返回在 dp 中最大值索引處的 ans 中儲存的子序列字串。

該方法有效地透過動態規劃構建可能的子序列，並確保在每一步中尊重群組不相等和海明距離的約束。結果即為滿足問題條件的最長字串子序列。

程式碼

C++

class Solution {
private:
    // 輔助函數，用於檢查兩個單詞的Hamming距離
    bool hammingDistanceCheck(const string& a, const string& b) {
        // 如果單詞長度不同，則Hamming距離不可能為1
        if (a.size() != b.size()) return false;

        int distance = 0; // 初始化Hamming距離
        for (size_t i = 0; i < a.size(); ++i) {
            // 如果當前位置的字符不同，則增加距離
            if (a[i] != b[i]) {
                if (++distance == 2) return false; // 超過一個差異則距離大於1
            }
        }
        return (distance == 1); // 如果正好一個差異則返回true
    }

public:
    // 主函數，用於查找最長子序列的單詞
    vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
        int len = words.size(); // 單詞列表的長度

        vector<int> dp(len, 1); // 動態規劃數組，存儲在每個索引結尾的最長子序列長度
        vector<vector<string>> ans(len); // 存儲潛在結果（單詞的子序列）

        // 用相應的單詞初始化每個子序列
        for (int i = 0; i < len; i++) {
            ans[i].emplace_back(words[i]);
        }

        // 遍歷每一對單詞以尋找有效的子序列
        for (int i = 1; i < len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                // 檢查形成有效子序列的條件
                if (groups[i] != groups[j] && dp[j] + 1 > dp[i] && hammingDistanceCheck(words[i], words[j])) {
                    dp[i] = dp[j] + 1; // 更新在索引i結尾的最長子序列長度
                    ans[i] = ans[j]; // 複製有效子序列
                    ans[i].emplace_back(words[i]); // 附加當前單詞
                }
            }
        }

        // 查找最長子序列的索引
        int maxIndex = max_element(dp.begin(), dp.end()) - dp.begin();
        return ans[maxIndex]; // 返回最長有效子序列
    }
};

Python

class Solution:
    # 輔助函數，用於檢查兩個單詞之間的海明距離
    def hammingDistanceCheck(self, a: str, b: str) -> bool:
        # 如果單詞長度不同，則海明距離不可能是1
        if len(a) != len(b):
            return False

        distance = 0  # 初始化海明距離
        for i in range(len(a)):
            # 如果當前位置的字符不同，增加距離
            if a[i] != b[i]:
                if distance == 1:
                    return False  # 超過一個不同，則距離大於1
                distance += 1
        return distance == 1  # 如果正好有一個不同，則返回true

    # 主函數，以找到最長的具有條件的子序列單詞
    def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        len_words = len(words)  # 單詞列表的長度

        dp = [1] * len_words  # 動態規劃陣列，存儲以每個索引結尾的最長子序列長度
        ans = [[] for _ in range(len_words)]  # 存儲潛在結果（單詞的子序列）

        # 用對應的單詞初始化每個子序列
        for i in range(len_words):
            ans[i].append(words[i])

        # 遍歷每對單詞以找到有效的子序列
        for i in range(1, len_words):
            for j in range(i - 1, -1, -1):
                # 檢查條件以形成有效的子序列
                if groups[i] != groups[j] and dp[j] + 1 > dp[i] and self.hammingDistanceCheck(words[i], words[j]):
                    dp[i] = dp[j] + 1  # 更新以索引i結尾的子序列的最大長度
                    ans[i] = ans[j][:]  # 複製有效子序列
                    ans[i].append(words[i])  # 添加當前單詞

        # 找到最長子序列的索引
        maxIndex = dp.index(max(dp))
        return ans[maxIndex]  # 返回最長的有效子序列

複雜度分析

時間複雜度: $O(n^2 \cdot m)$
該演算法使用巢狀迴圈結構來確定符合給定條件的最長子序列。以下是分步解析:
1. 初始化: 初始化 dp 陣列和 ans 向量需要 $O(n)$ 時間。
2. 巢狀迴圈: 主要計算涉及兩個巢狀迴圈遍歷單詞的索引。外層迴圈運行 $n$ 次迭代，對於每次迭代，內層迴圈最多可迭代 $i$ 次，在最壞情況下為 $n$ 次。這使得巢狀迴圈的時間複雜度約為 $O(n^2)$。
3. Hamming 距離檢查: 在內層迴圈中檢查每對單詞時，會調用 hammingDistanceCheck 函式。該函式本身會遍歷單詞的長度，最多為 $m = 10$（根據限制條件 $1 \leq words[i].length \leq 10$）。因此，Hamming 距離計算會貢獻一個 $O(m)$ 的因子。
綜合上述步驟，時間複雜度為 $O(n^2 \cdot m)$。
空間複雜度: $O(n \cdot m)$
1. DP 陣列: dp 陣列儲存每個單詞的整數以記錄在該索引結尾的最長子序列。這需要 $O(n)$ 空間。
2. 子序列儲存: ans 向量儲存單詞的子序列（字串的向量）。在最壞情況下，每個單詞都是它自己的子序列，使得空間複雜度為 $O(n \cdot m)$，其中 $m$ 是 words 中任一單詞的最大長度。
總體而言，空間複雜度為 $O(n \cdot m)$，因需要儲存每個索引的潛在最長子序列。

CS Note
En

Leetcode 2901. Longest Unequal Adjacent Groups Subsequence II

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析