题解-最长相邻不相等子序列 II

Problem:最长相邻不相等子序列

题目

给你一个整数 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 中的字符串长度可能 不相等 。

思路

– 注意到数据范围很小,1000,可用的复杂度较高

– 对于常见的求最长合法子序列可以用DP尝试(一般这种解法是$O(n^2)$)的

解题方法

1. 设计状态转移方程,设$dp[i]$表示以i为结尾的最长子序列的长度,由题意可知$$\\dp[i]=max(dp[j]+1)$$ $i$和$j$同时满足三个条件

    1. $j<i$

    2. $groups[i]!=groups[j]$

    3. $distance( words[i],words[j])==1$

2. 能得出答案的长度,为了得到字符串数组需要更多信息

3. 这里用pre数组记录每一个以$words[i]$为结尾的最长子序列的倒数第二个元素,如果不存在就为$-1$

> 时间复杂度,$O(n^2)$

> 空间复杂度,$O(n)$

code

将最后查找答案的那一步放在dp计算之中也可以保证计算正确

class Solution:
    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
        def isLegaldistance(a:str,b:str):
            #这里将两个条件混合起来,更方便一些
            if len(a)!=len(b):
                return False
            res=0
            for x,y in zip(a,b):
                if x!=y:
                    res+=1
                    if res>1:
                        return False
            return True
        #dp[i]表示以i为结尾的子序列的最大长度
        #pre[i]表示以i为结尾的子序列的倒数第二个元素在words中的序列
        resIndex=0
        dp=[1]*n
        pre=[-1]*n
        for i in range(n):
            s1=words[i]
            for j in range(i):
                if groups[i]!=groups[j] and dp[j]+1>dp[i] and isLegaldistance(s1,words[j]):
                    dp[i]=dp[j]+1
                    if (dp[i]>dp[resIndex]):
                        resIndex=i #只有更新时才有可能出现最大值
                    pre[i]=j
    res=[]
    while resIndex!=-1:
        res.append(words[resIndex])
        resIndex=pre[resIndex]
    return res[::-1]#从后向前做的遍历,所以要返回反转后数组</code></pre>