题解-最长不相等子序列 II-DP,时间On2,空间On

Problem: 100077. 最长相邻不相等子序列 II

• 思路
• 解题方法
• Code

思路

• 注意到数据范围很小,1000,可用的复杂度较高
• 对于常见的求最长合法子序列可以用DP尝试(一般这种解法是)的

解题方法

1. 设计状态转移方程,设表示以i为结尾的最长子序列的长度,由题意可知 和同时满足三个条件
2. 能得出答案的长度,为了得到字符串数组需要更多信息
3. 这里用pre数组记录每一个以为结尾的最长子序列的倒数第二个元素,如果不存在就为
   > 时间复杂度,
   > 空间复杂度,

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]#从后向前做的遍历,所以要返回反转后数组