C ++中最长的不常见子序列II

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串列表；我们必须找到其中最长的不常见子序列。最长的不常见子序列实际上是这些字符串之一的最长子序列，并且此子序列不应是其他字符串的任何子序列。

我们知道，子序列是一种序列，可以通过删除一些字符而不改变其余元素的顺序来从一个序列派生。

在这里，我们将获取一个字符串列表，并且输出必须是最长的不常见子序列的长度。如果没有最长的不常见子序列，则返回-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

      以上是 C ++中最长的不常见子序列II 的全部内容， 来源链接： utcz.com/z/345288.html

      回到顶部