Easy

题目描述

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

如果 words 的子序列中任意两个连续字符串在 groups 中对应索引的元素不同（即不能有连续的 0 或 1），则该子序列是交替的。

你的任务是从 words 中选择最长的交替子序列。

返回所选的子序列。如果有多个答案，返回其中任意一个。

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

示例 1：

输入：words = ["e","a","b"], groups = [0,0,1]
输出：["e","b"]
解释：可以选择子序列 ["e","b"]，因为 groups[0] != groups[2]。另一个可以选择的子序列是 ["a","b"]，因为 groups[1] != groups[2]。可以证明满足条件的最长索引子序列的长度是 2。

示例 2：

输入：words = ["a","b","c","d"], groups = [1,0,1,1]
输出：["a","b","c"]
解释：可以选择子序列 ["a","b","c"]，因为 groups[0] != groups[1] 且 groups[1] != groups[2]。另一个可以选择的子序列是 ["a","b","d"]，因为 groups[0] != groups[1] 且 groups[1] != groups[3]。可以证明满足条件的最长索引子序列的长度是 3。

约束条件：

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

提示：

  • 这个问题可以用贪心算法解决
  • 从 groups 的第一个数字开始构造答案
  • 对于范围 [1, n-1] 中的每个索引 i，如果 groups[i] != groups[i-1]，则将 i 添加到答案中

解题思路

解题思路

这道题目要求我们找到最长的交替子序列，其中"交替"的定义是相邻元素在 groups 数组中对应的值不同。

贪心策略分析

由于题目要求最长的交替子序列，我们可以使用贪心策略：

  1. 总是选择第一个元素作为起始点
  2. 从第二个元素开始遍历，如果当前元素与前一个选中元素在 groups 中的值不同，就将其加入结果

这个贪心策略是正确的，因为：

  • 如果当前位置可以选择（与前一个选中位置的 groups 值不同），那么选择它不会影响后续的选择
  • 跳过当前位置只会让序列变短，不会变长

算法步骤

  1. 初始化结果数组，添加第一个单词
  2. 记录上一个选中位置的 groups 值
  3. 从索引 1 开始遍历数组
  4. 如果当前位置的 groups 值与上一个选中位置不同，将当前单词加入结果
  5. 更新上一个选中位置的 groups 值

时间复杂度为 O(n)，空间复杂度为 O(1)（不计算结果数组）。

代码实现

class Solution {
public:
    vector<string> getLongestSubsequence(vector<string>& words, vector<int>& groups) {
        vector<string> result;
        result.push_back(words[0]);
        int lastGroup = groups[0];
        
        for (int i = 1; i < words.size(); i++) {
            if (groups[i] != lastGroup) {
                result.push_back(words[i]);
                lastGroup = groups[i];
            }
        }
        
        return result;
    }
};

class Solution:
    def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        result = [words[0]]
        last_group = groups[0]
        
        for i in range(1, len(words)):
            if groups[i] != last_group:
                result.append(words[i])
                last_group = groups[i]
        
        return result

public class Solution {
    public IList<string> GetLongestSubsequence(string[] words, int[] groups) {
        var result = new List<string> { words[0] };
        int lastGroup = groups[0];
        
        for (int i = 1; i < words.Length; i++) {
            if (groups[i] != lastGroup) {
                result.Add(words[i]);
                lastGroup = groups[i];
            }
        }
        
        return result;
    }
}

var getLongestSubsequence = function(words, groups) {
    const result = [words[0]];
    let lastGroup = groups[0];
    
    for (let i = 1; i < words.length; i++) {
        if (groups[i] !== lastGroup) {
            result.push(words[i]);
            lastGroup = groups[i];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次数组，其中 n 是数组长度
空间复杂度O(1)只使用常数额外空间，不计算返回结果的空间