C ++中最长的不常见子序列II
假设我们有一个字符串列表；我们必须找到其中最长的不常见子序列。最长的不常见子序列实际上是这些字符串之一的最长子序列，并且此子序列不应是其他字符串的任何子序列。
我们知道，子序列是一种序列，可以通过删除一些字符而不改变其余元素的顺序来从一个序列派生。
在这里，我们将获取一个字符串列表，并且输出必须是最长的不常见子序列的长度。如果没有最长的不常见子序列，则返回-1。
因此，如果输入像“aba”，“cdc”，“eae”，则输出将为3
为了解决这个问题，我们将遵循以下步骤-
定义一个函数isSubsequence()，这将需要a，b，
j：=0
对于初始化i：=0，当i<a的大小时，更新（将i增加1），执行-
（将j增加1）
如果j<b的大小并且a[i]与b[j]相同，则-
当b的大小与j相同时返回true
定义一个函数getDuplicates()，它将接受一个数组strs，
定义一组访问，另一组退出
对于初始化i：=0，当i<strs的大小时，更新（将i增加1），执行-
将strs[i]插入ret
如果访问了strs[i]，则-
将strs[i]插入访问
返回ret
从主要方法中，执行以下操作-
根据字符串长度对数组str进行排序
定义一组重复项：=getDuplicates(strs)
对于初始化i：=0，当i<strs的大小时，更新（将i增加1），执行-
如果isSubsequence（strs[j]，strs[i]）为假，则-
除此以外
strs的返回大小
如果j与i-1相同，则-
从循环中出来
strs的返回大小
忽略以下部分，跳至下一个迭代
如果strs[i]一式两份，则-
如果我等于0，则-
对于初始化j：=0，当j<i时，更新（将j增加1），执行-
返回-1
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(string a, string b){
return a.size() > b.size();
}
int findLUSlength(vector<string>& strs){
sort(strs.begin(), strs.end(), cmp);
set<string> duplicates = getDuplicates(strs);
for (int i = 0; i < strs.size(); i++) {
if (duplicates.count(strs[i]))
continue;
if (i == 0)
return strs[i].size();
for (int j = 0; j < i; j++) {
if (!isSubsequence(strs[j], strs[i])) {
if ((j == i - 1)) {
cout << i << endl;
return strs[i].size();
}
}
else
break;
}
}
return -1;
}
bool isSubsequence(string a, string b){
int j = 0;
for (int i = 0; i < a.size(); i++) {
if (j < b.size() && a[i] == b[j])
j++;
}
return j == b.size();
}
set<string> getDuplicates(vector<string>& strs){
set<string> visited;
set<string> ret;
for (int i = 0; i < strs.size(); i++) {
if (visited.count(strs[i])) {
ret.insert(strs[i]);
}
visited.insert(strs[i]);
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"aba", "cdc", "eae"};
cout << (ob.findLUSlength(v));
}输入值
{"aba", "cdc", "eae"}输出结果
3