資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
