@TOC1.题目1.题目描述最长的特殊序列II难度：中给定一个字符串列表strs，返回其中最长的特殊序列。如果最长的特殊序列不存在，则返回-1。特殊序列定义如下：该序列是一个字符串的唯一子序列（即不能是其他字符串的子序列）。s的子序列可以通过删除字符串s中的一些字符来实现。例如，“abc”是“aebdc”的子序列，因为可以去掉“aebdc”中的下划线字符得到“abc”。“aebdc”的子序列还包括“aebdc”、“aeb”和""（空字符串）。示例1：输入：strs=["aba","cdc","eae"]输出：3示例2：输入：strs=["aaa","aaa","aa"]输出：-1提示：2<=strs.length<=501<=strs[i].length<=10strs[i]只包含小写英文字母2.原题链接链接：522.最长的特殊序列二2.解题报告1.思路分析这道题的难点就在下面这道明显的，剩下的都是套路。让我从一个明显的开始：如果s的子序列ss是一个特殊的序列，那么s就更特殊了。因此，本题只需要判断每个字符串是否是其他字符串的子序列即可。如果一个字符串不是任何其他字符串的子序列，则该字符串本身就是一个可用于更新答案的特殊序列。最后，取所有特殊字符串的长度并找到最大值。如果不是，设置-1。子序列自动机每两个点对枚举一次，所以对于每个字符串，需要检查n-1个单独的字符串是否是它的子序列（不剪枝）。针对字符串多次检查子序列的方法可以使用子序列自动机。判断子序列的朴素方法是使用双指针i,j。i在原始字符串上，j在模式字符串上。我们发现当i向右移动时，必须先选择最近的（即最早的）等于p[j]的字符，每次的最差匹配复杂度为O(n+m)。那么我们就可以使用dp来预处理每个字符的下一个字符最早出现的位置。匹配时，我们可以直接将i指针移动到下一个匹配字符，跳过很多无用的比较。自动机构造的复杂度为O(mc)*，c=26是字典的长度，m是原字符串的长度。每场比赛的复杂度为O(n)。参考我的题解Python子序列自动机方法2.复杂性分析显然枚举点不能运行n^2。设平均字符串长度为m。双指针方法的复杂度为T(n)=O(n×n×2m)自动机方法，每个字符串只需要构造一次自动机，耗时m×26，然后剩下n-1个字符串进行匹配并消耗m，所以复杂度T(n)=O(n×(m×26+n×m))=O(n×n×m+n×m×26)主要的复杂度还是取决于外层n^2。节省的时间并不多diff=n×n×m-n×m×263。代码实现了子序列自动机。类SubSequenceAuto:def__init__(self,s,abc='abcdefghijklmnopqrstuvwxyz'):self.s,self.abc=s,abcself.n,abc_len=len(s),len(abc)self.abc_index={v:kfork,vinenumerate(abc)}self.dp=[[self.n]*abc_lenfor_inrange(self.n+1)]dp=self.dp#dp.append([self.n]*abc_len)foriinrange(self.n-1,-1,-1):dp[i]=dp[i+1][:]dp[i][self.abc_index[s[i]]]=i#forjinrange(abc_len):#dp[i][j]=iifs[i]==abc[j]elsedp[i+1][j]defquery_is_sub_seq(self,t):dp=self.dpabc_index=self.abc_indexn=self.nr=0forcint:r=dp[r][abc_index[c]]ifr==n:returnFalser+=1returnTrueclass解决方案：deffindLUSlength(self,strs:List[str])->int:"""先说一个显然：如果s的子序列ss是一个特殊序列，那么s更是特殊序列。因此，本题只需要判断每个字符串是否是其他字符串的子序列即可。判断子序列可以是双指针，也可以使用子序列自动机。"""n=len(strs)flags=[True]*n#每个字符串是否为特殊序列，初始化为0。如果是别人的子序列，则置False#下面判断j是否是i序列的子序列foriinrange(n):sba=SubSequenceAuto(strs[i])forjinrange(n):ifi==jorflags[j]==False:如果sba.query_is_sub_seq(strs[j])继续:flags[j]=Falseans=-1foriinrange(n):ifflags[i]:ans=max(ans,len(strs[i]))returnans3.本题总结1)后续自动机的方法可以优化判断子序列的时间，当字符串长度很大的时候优势很明显。但是这道题的数据很弱，所以优势不明显。2）如果有时间，写子序列自动机的模板四、参考链接前题：392.判断子序列人生苦短，我用Python！
