LeetCode刷题实战522：最长特殊序列 II
共 2836字，需浏览 6分钟
·
2022-02-12 06:16
Given an array of strings strs, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence does not exist, return -1.
An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.
A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.
For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).
示例
示例：
输入: "aba", "cdc", "eae"
输出: 3
提示：
所有给定的字符串长度不会超过 10 。
给定字符串列表的长度将在 [2, 50 ] 之间。
解题
class Solution {
public:
bool checkSubSeq(string a, string b) { // 判断字符串a是否是字符串b的子序列
for(int i = 0, j = 0; i < a.size(); ++i, ++j) {
while(j < b.size() && a[i] != b[j]) {
++j;
}
if(j == b.size()) { // 如果b走到最后也没有和a匹配完，那么a不是b的子序列
return false;
}
}
return true;
}
int findLUSlength(vector<string>& strs) {
sort(strs.begin(), strs.end(), [&](string a, string b) { // 将字符串数组按照字符串长度从大到小排序
if(a.size() != b.size()) {
return a.size() > b.size();
}
return a < b;
});
for(int i = 0; i < strs.size(); ++i) { // 按照字符串长度从大到小枚举所有的字符串
bool flag = true; // flag表示当前字符串是否是一个特殊序列
if(i + 1 < strs.size() && strs[i] == strs[i + 1]) { // 如果存在和这个字符串相同的字符串，则这个字符串不是特殊序列
flag = false;
continue;
}
for(int j = 0; j < i; ++j) { // 枚举所有长度比当前字符串大的字符串，判断当前字符串是否是其他字符串的子序列
if(checkSubSeq(strs[i], strs[j]) == true) {
flag = false;
}
}
if(flag == true) { // 找到了一个特殊序列，它的长度就是答案
return strs[i].size();
}
}
return -1;
}
};