共计 1844 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
这是 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 <= strs.length <= 50$
- $1 <= strs[i].length <= 10$
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 < n; i++) {if (strs[i].length() <= ans) continue;
boolean ok = true;
for (int j = 0; j < n && ok; j++) {if (i == j) continue;
if (check(strs[i], strs[j])) ok = false;
}
if (ok) ans = strs[i].length();}
return ans;
}
boolean check(String s1, String s2) {int n = s1.length(), m = s2.length();
if (m < n) return false;
int[][] f = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {f[i][j] = s1.charAt(i - 1) == s2.charAt(j - 1) ? f[i - 1][j - 1] + 1 : f[i - 1][j - 1];
f[i][j] = Math.max(f[i][j], f[i - 1][j]);
f[i][j] = Math.max(f[i][j], f[i][j - 1]);
if (f[i][j] == n) return true;
}
}
return false;
}
}- 工夫复杂度：查看每个 $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 多平台公布
