LeetCode-522 最长特殊序列 II

Table of Contents

LeetCode-522 最长特殊序列 II #

Solution 1 #

如果有一个特殊序列, 那么它所属的序列必然是一个长度不小于它的特殊序列, 因此判断初始序列的是否是其它序列的子序列即可.

代码如下:

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def is_subseq(s, t):
            i = 0
            for ch in t:
                if s[i] == ch:
                    i += 1
                    if i == len(s):
                        return True
            return False

        strs.sort(key=lambda x: -len(x))
        for i, s in enumerate(strs):
            is_valid = True
            for j, t in enumerate(strs):
                if i != j and is_subseq(s, t):
                    is_valid = False
                    break
            if is_valid:
                return len(s)
        return -1