难度: Medium
给定字符串列表 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] 只包含小写英文字母运行时间: 27 ms
内存: 16.0 MB
class Solution:
def findLUSlength(self, strs: List[str]) -> int:
def is_sub(s1, s2):
n, m, j = len(s1), len(s2), 0
for i in range(n):
if s1[i] == s2[j]:
j += 1
if j == m:
return True
return False
strs.sort(key=lambda x: (-len(x), x))
n, deleted = len(strs), set()
for i in range(n):
if i in deleted:
continue
if i + 1 < n and len(strs[i]) > len(strs[i + 1]):
return len(strs[i])
flag = True
for j in range(i + 1, n):
s1, s2 = strs[i], strs[j]
if is_sub(s1, s2):
deleted.add(j)
if flag and len(strs[j]) == len(strs[i]) and is_sub(s2, s1):
flag = False
if flag:
return len(strs[i])
return -1
该题解的思路是先将字符串数组按长度降序排序，然后遍历每个字符串，判断其是否是特殊序列。对于当前遍历到的字符串，如果它比下一个字符串长，那么它一定是特殊序列；否则，如果它不是任何其他字符串的子序列，那么它也是特殊序列。在判断子序列的过程中，可以通过双指针来实现。
时间复杂度: O(nlogn + n^2m^2)
空间复杂度: O(n)
class Solution:
def findLUSlength(self, strs: List[str]) -> int:
def is_sub(s1, s2):
n, m, j = len(s1), len(s2), 0
for i in range(n):
if s1[i] == s2[j]:
j += 1
if j == m:
return True
return False
# 按照长度降序排序字符串数组
strs.sort(key=lambda x: (-len(x), x))
n, deleted = len(strs), set()
for i in range(n):
if i in deleted:
continue
# 如果当前字符串比下一个字符串长，那么它一定是特殊序列
if i + 1 < n and len(strs[i]) > len(strs[i + 1]):
return len(strs[i])
flag = True
for j in range(i + 1, n):
s1, s2 = strs[i], strs[j]
# 判断当前字符串是否为其他字符串的子序列
if is_sub(s1, s2):
deleted.add(j)
# 判断其他字符串是否为当前字符串的子序列
if flag and len(strs[j]) == len(strs[i]) and is_sub(s2, s1):
flag = False
if flag:
return len(strs[i])
return -1
双指针技术用于效率地遍历两个字符串，以确定一个字符串是否是另一个字符串的子序列。具体实现中，设置两个指针i和j，分别指向两个字符串s1和s2的开始位置。遍历s1的过程中，每当s1的字符与s2的当前字符相匹配时，指针j向前移动一位。如果j移动到了s2的末尾，则说明s2是s1的子序列。如果遍历结束后j没有到达s2的末尾，说明s2不是s1的子序列。这种方法在性能上较优，因为它仅需要线性时间即可判断子序列关系。
在字符串数组按长度降序排序后，如果一个字符串长度大于紧跟其后的字符串，那么它不可能是任何长度更长的字符串的子序列，因为子序列的长度必然不会超过原字符串。此外，由于它比后续所有字符串都长，所以也不可能是后续任何字符串的子序列。因此，这样的字符串满足特殊序列的条件，即它不是数组中任何其他字符串的子序列。
当两个字符串长度相等时，判断它们是否互为子序列主要是通过检查它们是否完全相同。因为只有当两个相同长度的字符串完全一致时，它们才能互为子序列。在实现中，可以通过比较两个字符串是否相等来实现这一点。如果相等，它们互为子序列，否则不是。在给定的题解中，这种情况意味着当前字符串不是特殊序列，因为它至少与一个其他字符串相同。
使用集合`deleted`来记录被判断为子序列的字符串下标可以有效避免重复处理某些字符串，从而节省时间和计算资源。然而，这种方法确实会增加额外的空间复杂度，因为需要存储被删除的字符串的下标。在处理大量数据时，这可能会导致内存使用增加。但是，考虑到避免重复处理的时间节省，这通常是一个合理的权衡。如果数据量极大，可能需要考虑更高效的数据结构或优化算法以减少内存使用。