LeetCode 521. 最长特殊序列 Ⅰ
题目描述
原题：521. 最长特殊序列 Ⅰ。
给定两个小写英文字母字符串 a、b。特殊子序列是某个字符串的子序列，但不是另一个字符串的子序列。返回最长长度；不存在返回-1。输入字符为小写英文字母。
示例 1：
输入：a = "abc", b = "abd"
输出：3
解释："abc" 是自身的子序列，但不是 "abd" 的子序列，长度为 3。
示例 2：
输入：a = "abc", b = "abc"
输出：-1
解释：两个字符串相同，任意一个的子序列也一定是另一个的子序列。
提示：
- a、b 只含小写英文字母；子序列可以不连续，但必须保持原字符顺序。不存在特殊子序列时返回 -1。
题意分析
从两个输入字符串中的某一个选出一条子序列，要求它不能同时成为另一个字符串的子序列，返回这种特殊子序列的最长长度。子序列可以删除字符，但必须保留剩余字符的原有顺序；也允许一个字符都不删，直接选择整串。
要求只属于其中一个输入，而不是两者共同拥有。不存在任何符合条件的子序列时返回
-1，不能用零表示无解。
解法：比较整串是否相等
核心思路
[!blue]
若两个字符串完全相同，它们能生成的全部子序列也完全相同。从任意一侧选出的序列，另一侧同样拥有，因此不存在特殊子序列，直接返回
-1。若两个字符串长度不同，选择较长的完整字符串即可。它当然是自己的子序列，而较短的字符串不可能包含比自身还长的子序列，所以这个候选必然只属于较长的一侧。
若长度相同但内容不同，任意选择其中一个整串也合法。要从另一个等长字符串中选出相同长度的子序列，就必须保留全部字符，结果只能是另一个原串；既然两串不同，就不可能相互包含。
因此只要两串不相等，较长输入的整串就已经给出了长度为
max(a.length, b.length)的合法答案。任何子序列又都不可能超过其来源字符串长度，这个候选同时达到答案上界，所以无需枚举更短的子序列。
解题步骤
- 比较两个字符串的完整内容。
- 内容相同则返回
-1。- 内容不同则返回两个长度的较大值。
代码实现
class Solution {
public int findLUSlength(String a, String b) {
return a.equals(b) ? -1 : Math.max(a.length(), b.length());
}
}
func findLUSlength(a, b string) int {
if a == b {
return -1
}
return max(len(a), len(b))
}
复杂度分析
- 时间复杂度：最坏 $O(m)$，
m为较长字符串长度，主要用于相等判断。长度不同时可以直接判为不相等；长度相同时最坏需要逐字符比较。- 空间复杂度：$O(1)$，只比较字符串并读取长度，不生成候选子序列。
关键点总结
[!green]
- 整个输入也是它自己的子序列，可以先尝试长度最大的候选。
- 等长字符串互为完整子序列，当且仅当内容相同。
- 非相等时已有候选达到最大可能长度，相等时所有子序列都不符合要求。
易错点总结
[!yellow]
- 只比较长度是否相等，会漏掉等长但内容不同的合法情况。
- 把目标理解为最长公共子序列，求到的是两个输入都拥有的内容，方向相反。
- 以为子序列必须删除至少一个字符，会错过直接选整串的最优答案。
- Java 用
==判断字符串内容，会混淆对象引用与字符是否相同；这里使用equals。- 两串相同时返回零，未遵循题目无解时返回
-1的约定。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 522. 最长特殊序列 II | 中等 | 从两个字符串扩展到多个字符串后，不能只比较相等，还要检查候选是否为任意其他串的子序列。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！