leetcode：522. Longest special sequence II [greed + subsequence judgment]

analysis

Judge from the longest （ Ranking greed ）
If the current str, Not the rest str The subsequence , Then it is the longest special sequence
Two pointer tracing method is used to determine the subsequence , See if the small sequence can be completed

ac code

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

        # a Is it b The subsequence 
        #  Double pointer tracking （ classic ）
        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:]
            #  The current cannot be a subsequence of any other string ！
            for ss in nstrs:
                if isSubSequnce(strs[i], ss):
                    flag = False
                    break
            if flag:
                return len(strs[i])
        
        return -1

summary

Subsequence judgment + Sort greedy biggest start
Topic understanding ： The longest special sequence = The longest is not a sequence of other string subsequences
Small amount of data , Each of them can be judged （ From long to short is greed ）