Medium

题目描述

给你一个字符串数组 words 和一个数组 groups，两个数组的长度都为 n。

两个等长字符串的汉明距离是对应位置字符不同的位置数量。

你需要从索引数组 [0, 1, ..., n - 1] 中选择最长的子序列，使得对于表示为 [i0, i1, ..., ik-1] 长度为 k 的子序列，满足以下条件：

  • 对于子序列中的相邻索引，它们对应的组不相等，即对于每个满足 0 < j + 1 < k 的 j，都有 groups[ij] != groups[ij+1]。
  • 对于子序列中的所有相邻索引，words[ij] 和 words[ij+1] 长度相等，且它们之间的汉明距离为 1，其中 0 < j + 1 < k。

返回一个字符串数组，包含选定子序列中对应索引的单词（按顺序）。如果有多个答案，返回其中任何一个。

注意：words 中的字符串长度可能不相等。

示例 1：

输入：words = ["bab","dab","cab"], groups = [1,2,2]
输出：["bab","cab"]
解释：可以选择子序列 [0,2]。
- groups[0] != groups[2]
- words[0].length == words[2].length，且它们的汉明距离为 1。
所以，一个有效答案是 [words[0],words[2]] = ["bab","cab"]。

示例 2：

输入：words = ["a","b","c","d"], groups = [1,2,3,4]
输出：["a","b","c","d"]
解释：我们可以选择子序列 [0,1,2,3]。
它满足两个条件。

约束：

  • 1 <= n == words.length == groups.length <= 1000
  • 1 <= words[i].length <= 10
  • 1 <= groups[i] <= n
  • words 由不同的字符串组成
  • words[i] 由小写英文字母组成

解题思路

这道题是一个动态规划问题，需要找到满足条件的最长子序列。

核心思路：

  1. 使用动态规划，dp[i] 表示以 words[i] 结尾的最长有效子序列长度
  2. 对于每个位置 i，检查所有前面的位置 j，如果满足条件则更新 dp[i]
  3. 条件检查包括：组别不同、字符串等长、汉明距离为1

详细步骤：

  1. 汉明距离计算：遍历两个等长字符串，统计不同字符的位置数
  2. 状态转移：对于位置 i，遍历所有 j < i，如果 groups[i] != groups[j]、words[i].length == words[j].length 且汉明距离为1，则可以从 j 转移到 i
  3. 路径记录：使用 parent 数组记录每个位置的前驱，便于构造最终答案
  4. 答案构造：找到 dp 数组中的最大值位置，然后通过 parent 数组反向构造答案

时间复杂度分析：

  • 外层双重循环：O(n²)
  • 汉明距离计算：O(L)，其中 L 是字符串长度
  • 总时间复杂度：O(n² × L)

这个解法高效且易于理解，是处理此类带约束条件的最长子序列问题的标准方法。

代码实现

class Solution {
public:
    vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
        int n = words.size();
        vector<int> dp(n, 1);
        vector<int> parent(n, -1);
        
        auto hammingDistance = [](const string& a, const string& b) {
            if (a.length() != b.length()) return -1;
            int diff = 0;
            for (int i = 0; i < a.length(); i++) {
                if (a[i] != b[i]) diff++;
            }
            return diff;
        };
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (groups[i] != groups[j] && hammingDistance(words[i], words[j]) == 1) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        parent[i] = j;
                    }
                }
            }
        }
        
        int maxLen = 0, maxIdx = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                maxIdx = i;
            }
        }
        
        vector<string> result;
        int curr = maxIdx;
        while (curr != -1) {
            result.push_back(words[curr]);
            curr = parent[curr];
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        n = len(words)
        dp = [1] * n
        parent = [-1] * n
        
        def hamming_distance(a, b):
            if len(a) != len(b):
                return -1
            return sum(c1 != c2 for c1, c2 in zip(a, b))
        
        for i in range(1, n):
            for j in range(i):
                if groups[i] != groups[j] and hamming_distance(words[i], words[j]) == 1:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        parent[i] = j
        
        max_len = max(dp)
        max_idx = dp.index(max_len)
        
        result = []
        curr = max_idx
        while curr != -1:
            result.append(words[curr])
            curr = parent[curr]
        
        return result[::-1]

public class Solution {
    public IList<string> GetWordsInLongestSubsequence(string[] words, int[] groups) {
        int n = words.Length;
        int[] dp = new int[n];
        int[] parent = new int[n];
        
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            parent[i] = -1;
        }
        
        int HammingDistance(string a, string b) {
            if (a.Length != b.Length) return -1;
            int diff = 0;
            for (int i = 0; i < a.Length; i++) {
                if (a[i] != b[i]) diff++;
            }
            return diff;
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (groups[i] != groups[j] && HammingDistance(words[i], words[j]) == 1) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        parent[i] = j;
                    }
                }
            }
        }
        
        int maxLen = 0, maxIdx = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                maxIdx = i;
            }
        }
        
        List<string> result = new List<string>();
        int curr = maxIdx;
        while (curr != -1) {
            result.Add(words[curr]);
            curr = parent[curr];
        }
        
        result.Reverse();
        return result;
    }
}

var getWordsInLongestSubsequence = function(words, groups) {
    const n = words.length;
    const dp = new Array(n).fill(1);
    const parent = new Array(n).fill(-1);
    
    function hammingDistance(s1, s2) {
        if (s1.length !== s2.length) return -1;
        let diff = 0;
        for (let i = 0; i < s1.length; i++) {
            if (s1[i] !== s2[i]) diff++;
        }
        return diff;
    }
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (groups[i] !== groups[j] && hammingDistance(words[i], words[j]) === 1) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
        }
    }
    
    let maxLen = 0;
    let maxIndex = 0;
    for (let i = 0; i < n; i++) {
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIndex = i;
        }
    }
    
    const result = [];
    let curr = maxIndex;
    while (curr !== -1) {
        result.unshift(words[curr]);
        curr = parent[curr];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n² × L)
空间复杂度O(n)

其中 n 是数组长度，L 是字符串的最大长度。时间复杂度主要来自双重循环遍历所有位置对，以及每次比较时计算汉明距离的开销。空间复杂度主要用于存储 dp 数组和 parent 数组。