最长相邻不相等子序列 II

标签: 数组字符串动态规划

难度: Medium

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

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

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

相邻下标对应的 groups 值不同。即，对于所有满足 0 < j + 1 < k 的 j 都有 groups[i_j] != groups[i_{j + 1}] 。
对于所有 0 < j + 1 < k 的下标 j ，都满足 words[i_j] 和 words[i_{j + 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 <= n == words.length == groups.length <= 1000
1 <= words[i].length <= 10
1 <= groups[i] <= n
words 中的字符串 互不相同 。
words[i] 只包含小写英文字母。

Submission

运行时间: 481 ms

内存: 16.3 MB

class Solution:
    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
        def ok(s: str, t: str) -> bool:
            if len(s) != len(t):
                return False
            c = 0
            for a, b in zip(s, t):
                if a != b:
                    c += 1
                    if c > 1:
                        return False
            return c == 1

        # 定义 f[i] 表示从 i 到 n−1 中，我们选出的最长子序列的长度
        f = [0] * n
        from_idx = [0] * n
        mx = n - 1
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if f[j] > f[i] and groups[j] != groups[i] and ok(words[i], words[j]):
                    f[i] = f[j]
                    from_idx[i] = j
            f[i] += 1  # 加一写在这里
            if f[i] > f[mx]:
                mx = i

        ans = [''] * f[mx]
        for i in range(f[mx]):
            ans[i] = words[mx]
            mx = from_idx[mx]
        return ans

Explain

这个题解采用动态规划的方法来解决问题。定义 dp 数组 f[i] 为从索引 i 开始到 n-1，满足题目条件的最长子序列的长度。数组 from_idx 用来记录选择了哪个后续索引来形成最长子序列，便于最后重建答案。首先，需要一个辅助函数 ok(s, t) 来判断两个字符串的汉明距离是否为 1，即长度相同且恰好有一个字符不同。遍历每个单词，对于每个单词 i，再遍历所有可能的下一个单词 j (i < j)，检查是否满足 groups 值不同以及汉明距离为 1 的条件。如果满足，更新 f[i]。遍历完成后，通过 f 数组找到最长子序列的起始索引，然后使用 from_idx 数组重建整个子序列。

时间复杂度: O(n^2 * L)

空间复杂度: O(n)

class Solution:
    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
        # 判断两字符串汉明距离是否为1
        def ok(s: str, t: str) -> bool:
            if len(s) != len(t):
                return False
            c = 0
            for a, b in zip(s, t):
                if a != b:
                    c += 1
                    if c > 1:
                        return False
            return c == 1

        # 初始化 dp 数组和转移来源数组
        f = [0] * n
        from_idx = [0] * n
        mx = n - 1 # 最长序列的开始索引
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if f[j] > f[i] and groups[j] != groups[i] and ok(words[i], words[j]):
                    f[i] = f[j]
                    from_idx[i] = j
            f[i] += 1  # 包含自身
            if f[i] > f[mx]:
                mx = i

        # 重建答案
        ans = [''] * f[mx]
        for i in range(f[mx]):
            ans[i] = words[mx]
            mx = from_idx[mx]
        return ans

Explore

在动态规划中，数组 f[i] 用来记录从索引 i 开始的最长子序列的长度。初始化所有元素为 0 是因为在开始时，我们假设没有任何子序列可以从每个单词开始，即每个单词至少可以构成长度为1的子序列。在遍历过程中，f[i] 将根据条件逐渐更新，而初始化为 0 是一个安全的底线，确保在后续逻辑中，任何有效的子序列都会比初始值大，从而被正确更新。

从后向前遍历数组来更新 f[i] 的值能确保当更新 f[i] 时，所有可能的后续元素 f[j] (对于所有 j > i) 已经被计算过，因此可以直接使用它们的值来决定当前 f[i] 的最优值。这种从后向前的顺序是动态规划中常用的技巧，可以确保每次更新依赖的状态已经事先计算并存储好，从而有效地避免重复计算和潜在的错误。

在动态规划中，from_idx 数组用来记录每个位置 i 在构建最长子序列时选择的下一个词的索引 j。这样，在最终确定了最长子序列的起始点后，可以通过 from_idx 数组来追溯整个子序列的构成。具体地，从记录的起始点开始，通过连续访问 from_idx 指示的下一个索引，直至构建出整个序列。这种方式允许我们在不重新计算的情况下，直接通过记录的路径重建整个子序列。

是的，在 ok 函数的实现中首先检查了两个字符串 s 和 t 的长度是否相等。如果长度不相等，则直接返回 False，因为长度不同的字符串之间的汉明距离是未定义的。这个长度检查确保了只有长度相同的字符串才会进一步检验它们之间的字符差异，从而计算出恰好有一个字符不同的情况，即汉明距离为 1。