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