点击获取AI摘要

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

给定一个字符串数组 words ，和一个数组 groups ，两个数组长度都是 n 。

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

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

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

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

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

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

示例 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] 只包含小写英文字母。

问题分析

  • 从 words 和 groups 两个数组中，找出一个满足条件的最长子序列，并返回对应的字符串数组。
  1. groups 值相邻不同：选中的下标对应的 groups 值不能连续相同。
  2. words 相邻字符串的条件：
    • 长度相等。
    • 汉明距离为1（对应位置不同字符数为1）。
  • 返回满足条件的最长子序列对应的字符串数组。如果有多个，返回任意一个。

算法思路

建图＋最长路径

  • 将每个位置 ii 看作图中的一个节点；

  • 如果对于i<ji<j 满足

    1. groups[i] != groups[j]
    2. len(words[i]) == len(words[j]) 且二者汉明距离为 1

    则在节点 i→ji\to j 之间创建一条有向边。

  • 原问题即为在这一有向无环图（因为只允许 i<ji<j）中寻找一条最长路径，并返回该路径对应的单词序列。

动态规划实现

  • 令 dp[j] 表示以节点 jj 结尾的最长可行子序列的长度，prev[j] 记录前驱节点。

  • 初始时所有 dp[j]=1（单独选它自己）。

  • 对于每对 i<ji<j，若存在一条合法边，则

    1
    2
    3
    if dp[i] + 1 > dp[j]:
        dp[j] = dp[i] + 1
        prev[j] = i

    最终在所有 dp[j] 中取最大值所在的 j∗j^*，根据 prev 指针回溯即可得到完整子序列。

时间复杂度

  • 构建边和状态转移均需遍历所有 (i,j)(i,j) 对，总共 O(n2)O(n^2) 次判断；每次判断要比较长度并计算汉明距离，字符串长度最多 10，故总体 O(n2×L)O(n^2 \times L)，其中 L≤10L \le 10。

  • 空间复杂度 O(n)O(n)。

代码实现 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from typing import List

class Solution:
    def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        n = len(words)
        # dp[j]: 以 j 结尾的最长可行子序列长度
        dp = [1] * n
        prev = [-1] * n

        # 判断两个等长字符串汉明距离是否为 1
        def is_hamming1(a: str, b: str) -> bool:
            diff = 0
            for x, y in zip(a, b):
                if x != y:
                    diff += 1
                    if diff > 1:
                        return False
            return diff == 1

        # 双重循环做状态转移
        for j in range(n):
            for i in range(j):
                if groups[i] != groups[j] \
                   and len(words[i]) == len(words[j]) \
                   and is_hamming1(words[i], words[j]):
                    if dp[i] + 1 > dp[j]:
                        dp[j] = dp[i] + 1
                        prev[j] = i

        # 回溯最长路径
        end = max(range(n), key=lambda x: dp[x])
        res = []
        while end != -1:
            res.append(words[end])
            end = prev[end]
        return res[::-1]

思路与代码实现 2

我们还可以把问题抽象成「Word Ladder 最长路径」中的优化 DP，利用“模式”快速定位所有只差一个字符的候选，并在线性时间内完成状态转移。

模式哈希＋双最优值

  1. 模式生成

    对于每个单词 words[j]（长度为 LL），我们依次把它的第 kk 位用通配符 * 替换，生成 LL 个「模式」字符串：

    1
    2
    words[j] = “cab”
    patterns = [“*ab”, “c*b”, “ca*”]

    如果两个单词只在第 kk 位不同，那么它们都会映射到同一个模式。

  2. 记录每个模式下的「两类最优状态」

    • 对于每个模式 pp，我们维护两条记录：
      • best1[p] = (dp值最大的那个 (dp, group))
      • best2[p] = (次大 dp 的那个 (dp, group))
    • 这样，当我们处理一个新单词 j 时，只需要看它所有的 LL 个模式，对于每个模式：
      • 如果 best1[p].group != groups[j]，就可以用 best1[p].dp 做转移；
      • 否则就用 best2[p].dp 做转移。

  3. 状态转移

    1
    2
    3
    4
    5
    6
    7
    dp[j] = 1 + max(
        for each pattern p of words[j]:
            if best1[p].group ≠ groups[j]:
                best1[p].dp
            else:
                best2[p].dp
        , default=0)

    转移完成后，再用 (dp[j], groups[j]) 去更新 best1[p]/best2[p]。

  4. 时间复杂度

    • 每个单词生成和遍历 LL 个模式：O(n×L)O(n \times L)
    • 每个模式更新和查询常数次操作：O(1)O(1)
    • 整体：O(n×L)\boxed{O(n \times L)}，比 O(n2×L)O(n^2 \times L) 在 nn 达到几百时优势非常明显，其中 L=max⁡i∣wordsi∣≤10L=\max_i|words_i|\le10。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from collections import defaultdict
from typing import List, Tuple

class Solution:
    def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        n = len(words)
        # best1, best2: 模式 p -> (dp, group, index)
        best1: defaultdict[str, Tuple[int,int,int]] = defaultdict(lambda: (0, -1, -1))
        best2: defaultdict[str, Tuple[int,int,int]] = defaultdict(lambda: (0, -1, -1))
        
        dp = [1] * n
        prev = [-1] * n
        
        for j, w in enumerate(words):
            g = groups[j]
            # 找到能转移过来的最大 dp
            max_dp, max_i = 0, -1
            for k in range(len(w)):
                p = w[:k] + '*' + w[k+1:]
                d1, g1, i1 = best1[p]
                if g1 != g:
                    if d1 > max_dp:
                        max_dp, max_i = d1, i1
                else:
                    d2, g2, i2 = best2[p]
                    if d2 > max_dp:
                        max_dp, max_i = d2, i2
            
            dp[j] = max_dp + 1
            prev[j] = max_i
            
            # 更新每个模式下的 best1/best2
            for k in range(len(w)):
                p = w[:k] + '*' + w[k+1:]
                cand = (dp[j], g, j)
                b1 = best1[p]
                b2 = best2[p]
                if cand[0] > b1[0]:
                    best2[p] = b1
                    best1[p] = cand
                elif cand[0] > b2[0] and cand[1] != b1[1]:
                    best2[p] = cand
        
        # 回溯得到结果
        end = max(range(n), key=lambda x: dp[x])
        res = []
        while end != -1:
            res.append(words[end])
            end = prev[end]
        return res[::-1]