522 最长特殊序列 II（子序列）

短命女 2022-08-30 04:25 175阅读 0赞

**1. 问题描述：**

给定字符串列表，你需要从它们中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。输入将是一个字符串列表，输出是最长特殊序列的长度。如果最长特殊序列不存在，返回 -1 。

**示例：**

输入: "aba", "cdc", "eae"  
输出: 3

**提示：**

所有给定的字符串长度不会超过 10 。  
给定字符串列表的长度将在 \[2，50 \] 之间。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-uncommon-subsequence-ii

**2. 思路分析：**

这道题目与力扣521题是类似的，这道题目是有n个字符串，我们需要在这n个字符串中找到不是其他字符串的最长的子序列，这里我们也可以考虑答案是否是在者n个字符串中的一个，分析可以发现答案可能是在这n个字符串中的一个（有可能答案不存在），为什么呢？因为如果一个序列的子序列是特殊序列，那么当前的序列肯定也是特殊序列，因为当前的子序列是更长的，所以我们只需要在n个字符串中找答案即可，如何快速判断一个字符串是否是另外一个字符串的子序列呢？这里可以使用双指针算法。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 双指针算法判断字符串a是否是b的子序列
        def check(self, a: str, b: str):
            k = 0
            for i in range(len(b)):
                if k < len(a) and a[k] == b[i]: k += 1
            return k == len(a)
    
        def findLUSlength(self, w: List[str]) -> int:
            res = -1
            for i in range(len(w)):
                is_sub = 0
                for j in range(len(w)):
                    # 判断当前的字符串是否是另外一个字符串的子序列
                    if i != j and self.check(w[i], w[j]):
                        is_sub = 1
                if is_sub == 0: res = max(res, len(w[i]))
            return res