数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的最长不公共子序列
假设我们有一组字符串；我们需要找到它们之间最长的不公共子序列。最长的不公共子序列实际上是这些字符串之一的最长子序列，并且此子序列不应该是其他字符串的任何子序列。
我们知道子序列是从一个序列中删除一些字符而不改变剩余元素的顺序而派生的序列。
这里我们将获取一个字符串列表，输出需要是最长不公共子序列的长度。如果没有最长不公共子序列，则返回 -1。
因此，如果输入类似于“aba”、“cdc”、“eae”，则输出将为 3
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 isSubsequence()，它将获取 a、b，
j := 0
对于初始化 i := 0，当 i < a 的大小，更新（i 增加 1），执行：
如果 j < b 的大小并且 a[i] 与 b[j] 相同，则：
（j 增加 1）
当 b 的大小与 j 相同时返回 true
定义一个函数 getDuplicates()，它将获取一个数组 strs，
定义一个集合 visited 和另一个集合 ret
对于初始化 i := 0，当 i < strs 的大小，更新（i 增加 1），执行：
如果 strs[i] 位于 visited 中，则：
将 strs[i] 插入 ret
将 strs[i] 插入 visited
返回 ret
从主方法中，执行以下操作：
根据字符串长度对数组 strs 进行排序
定义一个集合 duplicates := getDuplicates(strs)
对于初始化 i := 0，当 i < strs 的大小，更新（i 增加 1），执行：
如果 strs[i] 位于 duplicates 中，则：
忽略以下部分，跳到下一轮迭代
如果 i 等于 0，则：
返回 strs[i] 的大小
对于初始化 j := 0，当 j < i，更新（j 增加 1），执行：
如果 isSubsequence(strs[j], strs[i]) 为假，则：
如果 j 等于 i - 1，则：
返回 strs[i] 的大小
否则
退出循环
返回 -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
102 次查看
