LeetCode 题解工作台
最长特殊序列 II
给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。 特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列） 。 s 的 子序列 可以通过删去字符串 s 中的某些字符实现。 例如， "abc" 是 "aebdc" 的子序列，因…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们定义一个函数 $check(s, t)$，用于判断字符串 是否是字符串 的子序列。我们可以使用双指针的方法，初始化两个指针 和 分别指向字符串 和字符串 的开头，然后不断移动指针 ，如果 和 相等，则移动指针 ，最后判断 是否等于 的长度即可。若 等于 的长度，则说明 是 的子序列。 判断字符串 是否独有，只需要取字符串 本身，与字符串列表的其他字符串比较即可。…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定字符串列表 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]只包含小写英文字母
解题思路
方法一：判断子序列
我们定义一个函数 ，用于判断字符串 是否是字符串 的子序列。我们可以使用双指针的方法，初始化两个指针 和 分别指向字符串 和字符串 的开头，然后不断移动指针 ，如果 和 相等，则移动指针 ，最后判断 是否等于 的长度即可。若 等于 的长度，则说明 是 的子序列。
判断字符串 是否独有，只需要取字符串 本身，与字符串列表的其他字符串比较即可。如果存在 是其他字符串的子序列，则 不是独有的。否则，字符串 是独有的。我们取所有独有字符串中长度最长的字符串即可。
时间复杂度 ，其中 是字符串列表的长度，而 是字符串的平均长度。空间复杂度 。
class Solution:
def findLUSlength(self, strs: List[str]) -> int:
def check(s: str, t: str):
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
ans = -1
for i, s in enumerate(strs):
for j, t in enumerate(strs):
if i != j and check(s, t):
break
else:
ans = max(ans, len(s))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2 * l) where n is the number of strings and l is the maximum string length due to pairwise subsequence checks. Space complexity is O(n * l) for storing strings and hash maps used in the lookup process. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks if you considered sorting strings by length to optimize finding the longest uncommon subsequence.
- question_mark
Checks whether you correctly handle duplicates and identical strings affecting subsequence detection.
- question_mark
Tests understanding of subsequence verification and how to efficiently skip impossible candidates.
常见陷阱
外企场景- error
Failing to sort strings, leading to returning a shorter uncommon subsequence instead of the longest.
- error
Incorrectly identifying a string as uncommon when it is a subsequence of another, especially with duplicates.
- error
Overlooking edge cases where all strings are identical or nested subsequences exist, resulting in missing the -1 return case.
进阶变体
外企场景- arrow_right_alt
Consider a version where strings contain uppercase letters or digits requiring adjusted hash checks.
- arrow_right_alt
Allow extremely long strings requiring optimized two-pointer subsequence verification instead of naive scans.
- arrow_right_alt
Find the second-longest uncommon subsequence instead of the longest, changing scan termination logic.