LC 521. 最长特殊序列 Ⅰ
题目描述
这是 LeetCode 上的 521. 最长特殊序列 Ⅰ ,难度为 简单。
给你两个字符串 a
和 b
,请返回 这两个字符串中 最长的特殊序列 。如果不存在,则返回 $-1$ 。
「最长特殊序列」 定义如下:该序列为 某字符串独有的最长子序列(即不能是其他字符串的子序列) 。
字符串 s
的子序列是在从 s
中删除任意数量的字符后可以获得的字符串。
例如,“abc”
是 “aebdc”
的子序列,因为您可以删除 “aebdc”
中的下划线字符来得到 “abc”
。 “aebdc”
的子序列还包括 “aebdc”
、 “aeb”
和 “”
(空字符串)。
示例 1:1
2
3
4
5输入: a = "aba", b = "cdc"
输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc"),两者均为自身的子序列且不是对方的子序列。
示例 2:1
2
3
4
5输入:a = "aaa", b = "bbb"
输出:3
解释: 最长特殊序列是“aaa”和“bbb”。
示例 3:1
2
3
4
5输入:a = "aaa", b = "aaa"
输出:-1
解释: 字符串a的每个子序列也是字符串b的每个子序列。同样,字符串b的每个子序列也是字符串a的子序列。
提示:
- $1 <= a.length, b.length <= 100$
a
和b
由小写英文字母组成
脑筋急转弯
当两字符串不同时,我们总能选择长度不是最小的字符串作为答案,而当两字符串相同时,我们无法找到特殊序列。
代码:1
2
3
4
5class Solution {
public int findLUSlength(String a, String b) {
return a.equals(b) ? -1 : Math.max(a.length(), b.length());
}
}
- 时间复杂度:字符串比较复杂度与长度成正比,复杂度为 $O(\max(n, m))$
- 空间复杂度:$O(1)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.521
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!