leetcode：522. 最长特殊序列 II【贪心 + 子序列判断】

分析

从最长开始来判断（排序贪心）
如果当前的str，不是其余str的子序列，那么它就是最长的特殊序列
子序列的判断使用双指针追踪方法，看看小的序列能不能走完即可

ac code

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:

        # a是否为b的子序列
        # 双指针追踪（经典）
        def isSubSequnce(a, b):
            n, m = len(a), len(b)
            i = j = 0
            while i < n and j < m:
                if a[i] == b[j]:
                    i += 1
                j += 1
            return i == n
        
        n = len(strs)
        strs.sort(key = lambda x: -len(x))
        #res = -1
        for i in range(n):
            flag = True
            nstrs = strs[:i] + strs[i + 1:]
            # 当前的不能是其他任何字符串的子序列！
            for ss in nstrs:
                if isSubSequnce(strs[i], ss):
                    flag = False
                    break
            if flag:
                return len(strs[i])
        
        return -1

总结

子序列判断 + 排序贪心最大开始
题目理解：最长特殊序列 = 最长的不是其他字符串子序列的序列
数据量小，每个拿出来判断一下即可（从长往短是贪心）