0522. Longest Uncommon Subsequence II
=====================================
题目信息
--------
:题号: 0522
:难度: Medium
:主题: 字符串数组、子序列、候选排除、重复字符串
:原题: `LeetCode 0522 `_
:重点: 候选必须是某个字符串的子序列且不是其他任何字符串的子序列、重复字符串会互相排除、返回最大长度
题目重述
--------
给定字符串数组 ``strs``。寻找一个字符串,使它是数组中某一个字符串的子序列,同时不是数组中其他任何字符串的子序列;返回所有这类不公共子序列中的最大长度。
若不存在符合条件的子序列,返回 ``-1``。同一个文本若在数组中出现多次,则它作为完整字符串时会是另一份相同字符串的子序列,不能直接成为不公共候选。只需返回长度,不返回具体字符串。
自建示例
--------
最长字符串不属于其他字符串:
.. code-block:: text
输入:strs = ["abcd","abc","ab","xy"]
输出:4
解释:"abcd" 是自身的子序列,但不是其他任一字符串的子序列,因此答案为其长度 4。
重复字符串使所有候选失效:
.. code-block:: text
输入:strs = ["aa","aa","a"]
输出:-1
解释:每个 "aa" 都是另一份 "aa" 的子序列,而 "a" 又是 "aa" 的子序列,因此没有不公共子序列。
只需检验每个原字符串本身
------------------------
若某个字符串存在不公共子序列,取它的完整字符串本身即可得到不短于该候选的结果;因此只需把每个 ``strs[i]`` 当作候选,检查它是否是其他任何字符串的子序列。候选按长度降序检查,第一枚通过者就是最大长度。
检查时必须跳过自身,但不能跳过内容相同的另一项;重复字符串会互相包含,因而都不能通过。用双指针判断一个字符串是否为另一个字符串的子序列。
C++ 实现
--------
.. code-block:: cpp
class Solution {
bool isSubsequence(const std::string& candidate,
const std::string& source) {
int i = 0;
for (char character : source) {
if (i < static_cast(candidate.size()) &&
candidate[i] == character) {
++i;
}
}
return i == static_cast(candidate.size());
}
public:
int findLUSlength(std::vector& strs) {
std::vector order(strs.size());
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(),
[&](int left, int right) {
return strs[left].size() > strs[right].size();
});
for (int i : order) {
bool uncommon = true;
for (int j = 0; j < static_cast(strs.size()); ++j) {
if (i != j && isSubsequence(strs[i], strs[j])) {
uncommon = false;
break;
}
}
if (uncommon) return strs[i].size();
}
return -1;
}
};
代码分析
--------
完整字符串是其自身所有子序列中最长的一个,所以检验原字符串不会错过最优答案;跳过自身且保留重复项检查,准确表达“其他字符串”的约束。设字符串数为 ``m``、最大长度为 ``L``,排序后判断时间复杂度为 ``O(m^2 L)``,额外空间为 ``O(m)``。