题目链接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 :输入n3,words[bab,dab,cab],groups[1,2,2]输出[bab,cab]解释一个可行的子序列是[0,2]。-groups[0]!groups[2]-words[0].lengthwords[2].length 且它们之间的汉明距离为1。 所以一个可行的答案是[words[0],words[2]][bab,cab]。 另一个可行的子序列是[0,1]。-groups[0]!groups[1]-words[0].lengthwords[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] 。 它是所有下标子序列里最长且满足所有条件的。 所以它是唯一的答案。解题思路问题理解给定一个字符串数组words和一个整数数组groups其中groups[i]表示words[i]的分组。需要找到一个子序列满足相邻元素的group值不同。相邻字符串的汉明距离为1即仅有一个字符不同。子序列需要是最长的包含尽可能多的元素。关键思路动态规划从后向前计算每个位置i的最长子序列长度f[i]并记录转移路径from[i]。汉明距离检查确保相邻字符串仅有一个字符不同。贪心优化在动态规划过程中优先选择能构成更长序列的后续元素。算法流程初始化f数组存储长度和from数组存储转移路径。从后向前遍历数组对于每个i检查所有j i如果满足条件分组不同且汉明距离为1则更新f[i]和from[i]。包含当前单词后更新最长子序列的起始索引maxI。根据from数组构建结果列表。题解代码classSolution{publicListStringgetWordsInLongestSubsequence(String[]words,int[]groups){intnwords.length;// f[i] 表示以 words[i] 开头的最长子序列长度int[]fnewint[n];// from[i] 表示 words[i] 在子序列中的下一个单词的索引int[]fromnewint[n];// 记录最长子序列的起始索引intmaxIn-1;// 从后向前动态规划for(intin-1;i0;i--){for(intji1;jn;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]){maxIi;// 更新最长子序列的起始索引}}// 构建结果列表intimaxI;intmf[i];ListStringansnewArrayList(m);// 预分配空间for(intk0;km;k){ans.add(words[i]);ifrom[i];}returnans;}// 检查两个字符串的汉明距离是否为1privatebooleancheck(Strings,Stringt){if(s.length()!t.length()){returnfalse;}booleandifffalse;for(inti0;is.length();i){if(s.charAt(i)!t.charAt(i)){if(diff){// 汉明距离大于1returnfalse;}difftrue;}}returndiff;// 汉明距离为1}}复杂度分析时间复杂度动态规划的双重循环O(n²)其中n是数组长度。每次汉明距离检查O(L)其中L是字符串的平均长度。总时间复杂度O(n² * L)。空间复杂度f和from数组O(n)。结果列表O(n)最坏情况下。总空间复杂度O(n)。