2901. 最长相邻不相等子序列 II

题目链接

2901. 最长相邻不相等子序列 II - 力扣（LeetCode）

题目描述

给你一个整数n和一个下标从 0 开始的字符串数组words，和一个下标从 0 开始的数组groups，两个数组长度都是n。

两个长度相等字符串的 汉明距离 定义为对应位置字符 不同 的数目。

你需要从下标[0, 1, ..., n - 1]中选出一个 最长子序列 ，将这个子序列记作长度为k的[i0, i1, ..., ik - 1]，它需要满足以下条件：

• 相邻 下标对应的groups值 不同。即，对于所有满足0 < j + 1 < k的j都有groups[ij] != groups[ij + 1]。
• 对于所有0 < j + 1 < k的下标j，都满足words[ij]和words[ij + 1]的长度 相等 ，且两个字符串之间的 汉明距离 为1。

请你返回一个字符串数组，它是下标子序列 依次 对应words数组中的字符串连接形成的字符串数组。如果有多个答案，返回任意一个。

子序列 指的是从原数组中删掉一些元素，剩余元素不改变相对位置得到的新的数组。

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

题目示例

示例 1 :

输入：n=3,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"]。 另一个可行的子序列是[0,1]。-groups[0]!=groups[1]-words[0].length=words[1].length 且它们之间的汉明距离为1。 所以另一个可行的答案是[words[0],words[1]]=["bab","dab"]。 符合题意的最长子序列的长度为2。

示例 2 :

输入：n = 4, 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. 问题理解：
   • 给定一个字符串数组words和一个整数数组groups，其中groups[i]表示words[i]的分组。
   • 需要找到一个子序列，满足：
     • 相邻元素的group值不同。
     • 相邻字符串的汉明距离为1（即仅有一个字符不同）。
   • 子序列需要是最长的（包含尽可能多的元素）。
2. 关键思路：
   • 动态规划：从后向前计算每个位置i的最长子序列长度f[i]，并记录转移路径from[i]。
   • 汉明距离检查：确保相邻字符串仅有一个字符不同。
   • 贪心优化：在动态规划过程中，优先选择能构成更长序列的后续元素。
3. 算法流程：
   • 初始化f数组（存储长度）和from数组（存储转移路径）。
   • 从后向前遍历数组：
     • 对于每个i，检查所有j > i，如果满足条件（分组不同且汉明距离为1），则更新f[i]和from[i]。
     • 包含当前单词后，更新最长子序列的起始索引maxI。
   • 根据from数组构建结果列表。

题解代码

classSolution{publicList<String>getWordsInLongestSubsequence(String[]words,int[]groups){intn=words.length;// f[i] 表示以 words[i] 开头的最长子序列长度int[]f=newint[n];// from[i] 表示 words[i] 在子序列中的下一个单词的索引int[]from=newint[n];// 记录最长子序列的起始索引intmaxI=n-1;// 从后向前动态规划for(inti=n-1;i>=0;i--){for(intj=i+1;j<n;j++){// 检查是否满足条件：分组不同且汉明距离为1if(f[j]>f[i]&&groups[j]!=groups[i]&&check(words[i],words[j])){f[i]=f[j];from[i]=j;}}f[i]++;// 包含当前单词if(f[i]>f[maxI]){maxI=i;// 更新最长子序列的起始索引}}// 构建结果列表inti=maxI;intm=f[i];List<String>ans=newArrayList<>(m);// 预分配空间for(intk=0;k<m;k++){ans.add(words[i]);i=from[i];}returnans;}// 检查两个字符串的汉明距离是否为1privatebooleancheck(Strings,Stringt){if(s.length()!=t.length()){returnfalse;}booleandiff=false;for(inti=0;i<s.length();i++){if(s.charAt(i)!=t.charAt(i)){if(diff){// 汉明距离大于1returnfalse;}diff=true;}}returndiff;// 汉明距离为1}}

复杂度分析

1. 时间复杂度：
   • 动态规划的双重循环：O(n²)，其中n是数组长度。
   • 每次汉明距离检查：O(L)，其中L是字符串的平均长度。
   • 总时间复杂度：O(n² * L)。
2. 空间复杂度：
   • f和from数组：O(n)。
   • 结果列表：O(n)（最坏情况下）。
   • 总空间复杂度：O(n)。