题目描述
这是 LeetCode 上的 522. 最长特殊序列 II ，难度为 中等。
Tag : 「LCS」、「最长公共子序列」、「序列 DP」、「枚举」、「动态规划」
给定字符串列表 strs，返回其中 最长的特殊序列 。如果最长特殊序列不存在，返回 $-1$ 。
特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。
s 的 子序列可以通过删去字符串 s 中的某些字符实现。
- 例如，
"abc"是"aebdc"的子序列，因为您可以删除"aebdc"中的下划线字符来得到"abc"。"aebdc"的子序列还包括"aebdc"、"aeb"和""(空字符串)。
示例 1：
输入: strs = ["aba","cdc","eae"]
输出: 3示例 2:
输入: strs = ["aaa","aaa","aa"]
输出: -1提示:
- $2
- $1
-
strs[i]只包含小写英文字母
LCS
记 strs 数组长度为 $n$，单个 $strs[i]$ 的最大长度 $m$。其中 $n$ 数据范围为 $50$，$m$ 数据范围为 $10$。
根据题意，我们可以枚举每个 $s1 = str[i]$，检查其是否为其他 $s2 = strs[j]$ 的子序列，这需要枚举所有点对，复杂度为 $O(n^2)$。同时记录遍历过程中的最大长度 ans，用于剪枝（对于字符串长度本身小于等于 ans 的 $strs[i]$ 可直接跳过）。
我们可以实现一个 check 函数来检查 s1 是否为 s2 的子序列，该问题可转化为求 s1 和 s2 的最长公共子序列长度。若最长公共子序列长度为 s1 长度，说明 s1 为 s2 的子序列，此时 $strs[i]$ 不满足条件，否则我们使用 $strs[i]$ 的长度来更新 ans。check 函数的复杂度为 $O(m^2)$。
不了解 LCS 的同学可以看前置 🧀 : LCS 模板题
因此总的计算量为 $n^2 times m^2 = 2.5 times 10^5$，可以过。
代码：
class Solution {
public int findLUSlength(String[] strs) {
int n = strs.length, ans = -1;
for (int i = 0; i - 时间复杂度：检查每个 $strs[i]$ 是否符合要求，需要枚举所有的点对，复杂度为 $O(n^2)$；求解 LCS 问题的复杂度为 $O(m^2)$。整体复杂度为 $O(n^2 times m^2)$
- 空间复杂度：$O(m^2)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.522 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
本文由mdnice多平台发布
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
