LeetCode 题解工作台
最长相邻不相等子序列 I
给定一个字符串数组 words ，和一个 二进制 数组 groups ，两个数组长度都是 n 。 如果 words 的一个 子序列 是交替的，那么对于序列中的任意两个连续字符串，它们在 groups 中相同索引的对应元素是 不同 的（也就是说，不能有连续的 0 或 1）， 你需要从 words 中选…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 状态·转移·动态规划
答案摘要
我们可以遍历数组 ，对于当前遍历到的下标 ，如果 或者 $groups[i] \neq groups[i - 1]$，我们就将 加入答案数组中。 时间复杂度 ，空间复杂度 。其中 是数组 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个字符串数组 words ，和一个 二进制 数组 groups ，两个数组长度都是 n 。
如果 words 的一个 子序列 是交替的，那么对于序列中的任意两个连续字符串，它们在 groups 中相同索引的对应元素是 不同 的（也就是说，不能有连续的 0 或 1），
你需要从 words 中选出 最长交替子序列。
返回选出的子序列。如果有多个答案，返回 任意 一个。
注意：words 中的元素是不同的 。
示例 1：
输入：words = ["e","a","b"], groups = [0,0,1] 输出：["e","b"] 解释：一个可行的子序列是 [0,2] ，因为 groups[0] != groups[2] 。 所以一个可行的答案是 [words[0],words[2]] = ["e","b"] 。 另一个可行的子序列是 [1,2] ，因为 groups[1] != groups[2] 。 得到答案为 [words[1],words[2]] = ["a","b"] 。 这也是一个可行的答案。 符合题意的最长子序列的长度为 2 。
示例 2：
输入：words = ["a","b","c","d"], groups = [1,0,1,1] 输出：["a","b","c"] 解释：一个可行的子序列为 [0,1,2] 因为 groups[0] != groups[1] 且 groups[1] != groups[2] 。 所以一个可行的答案是 [words[0],words[1],words[2]] = ["a","b","c"] 。 另一个可行的子序列为 [0,1,3] 因为 groups[0] != groups[1] 且 groups[1] != groups[3] 。 得到答案为 [words[0],words[1],words[3]] = ["a","b","d"] 。 这也是一个可行的答案。 符合题意的最长子序列的长度为 3 。
提示：
1 <= n == words.length == groups.length <= 1001 <= words[i].length <= 10groups[i]是0或1。words中的字符串 互不相同 。words[i]只包含小写英文字母。
解题思路
方法一：贪心 + 一次遍历
我们可以遍历数组 ，对于当前遍历到的下标 ，如果 或者 ，我们就将 加入答案数组中。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
return [words[i] for i, x in enumerate(groups) if i == 0 or x != groups[i - 1]]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for understanding of dynamic programming with state transitions.
- question_mark
Evaluate how well the candidate applies the greedy approach in practice.
- question_mark
Assess whether the candidate can identify and avoid unnecessary computations to maintain efficiency.
常见陷阱
外企场景- error
Failing to properly track the alternating sequence when encountering elements with the same group value.
- error
Overcomplicating the solution with unnecessary nested loops or data structures.
- error
Not taking advantage of the greedy nature of the problem, leading to suboptimal subsequences.
进阶变体
外企场景- arrow_right_alt
Consider variations where the input contains multiple possible subsequences with different lengths.
- arrow_right_alt
Explore alternative solutions where the goal is to find subsequences that maximize both length and distinctness of elements.
- arrow_right_alt
Consider a version of the problem with larger input sizes, testing the efficiency of the solution.