[LeetCode] 每日一题 2901. 最长相邻不相等子序列 II（动态规划）

题目描述

给定一个字符串数组 words ，和一个数组 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 中的字符串长度可能 不相等 。

题目链接

https://leetcode.cn/problems/longest-unequal-adjacent-groups-subsequence-ii

示例输入

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

示例 2

输入：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 <= n == words.length == groups.length <= 1000

• 1 <= words[i].length <= 10

• 1 <= groups[i] <= n

• words 中的字符串 互不相同 。

• words[i] 只包含小写英文字母。

解题思路

这题相较昨天明显复杂了许多。起初我并没有什么明确的思路，尝试用回溯法进行暴力搜索，虽然逻辑简单，但显然超时了。

后来参考评论区的提示，我意识到这题其实和一种较少见的动态规划套路很像：我们可以从后往前遍历，假设当前元素是子序列的起点，计算以它为起点时子序列的最大长度。

关键点在于如何处理这两个条件：

1. 相邻元素 group 不同

2. 相邻字符串长度相等，且汉明距离为 1

我们用一个 dp[i] 数组记录从 i 开始能形成的最长子序列长度，并用一个 next[i] 数组记录最优路径的下一个元素索引，最终通过 next 还原路径。

这种写法相当于先构建“有向图”，然后找一条最长路径，思想和拓扑DP有点相似。

代码实现

class Solution {
    public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {
        int n = words.length;
        int[] dp = new int[n];
        int[] next = new int[n];
        int maxStart = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (dp[j] > dp[i] && groups[j] != groups[i] && check(words[i], words[j])) {
                    dp[i] = dp[j];
                    next[i] = j;
                }
            }
            dp[i]++;
            if (dp[i] > dp[maxStart]) {
                maxStart = i;
            }
        }
        int temp = maxStart;
        List<String> ans = new ArrayList<>(dp[maxStart]);
        for (int i = 0; i < dp[maxStart]; i++) {
            ans.add(words[temp]);
            temp = next[temp];
        }
        return ans;
    }

    private boolean check(String a, String b) {
        if (a.length() != b.length()) {
            return false;
        }
        int n = a.length();
        boolean diff = false;
        for (int i = 0; i < n; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                if (diff) {
                    return false;
                }
                diff = true;
            }
        }
        return diff;
    }
}

复杂度分析

• 时间复杂度：

  • O(n² * m)，其中 n 是 words 的长度，m 是字符串的平均长度。嵌套循环加上 check() 的比对

• 空间复杂度：

  • O(n)，用来存储 dp 和 next 数组

总结

这题真正的难点在于“选择一个元素会影响后续选择”，因此暴力回溯很容易陷入指数级时间复杂度。切换思路之后，我发现从尾到头做动态规划，并记录路径，是解决此类题型的关键。

顺便复习了一个老知识点：如何重建最长路径的具体内容 —— 用一个 next[] 数组真的非常好用！

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。