C++で最長の珍しいサブシーケンスII

文字列のリストがあるとします。それらの中で最も長い珍しいサブシーケンスを見つける必要があります。最長の珍しいサブシーケンスは、実際にはこれらの文字列の1つの最長のサブシーケンスであり、このサブシーケンスは他の文字列のサブシーケンスであってはなりません。

サブシーケンスは、残りの要素の順序を変更せずに一部の文字を削除することで、1つのシーケンスから派生できるシーケンスであることがわかっています。

ここでは文字列のリストを取得します。出力は、最も長い珍しいサブシーケンスの長さである必要があります。最長の珍しいサブシーケンスがない場合は、-1を返します。

したがって、入力が「aba」、「cdc」、「eae」のような場合、出力は3になります

これを解決するには、次の手順に従います-

• 関数isSubsequence（）を定義します。これには、a、b、

  が必要です。

• j：=0

• 初期化i：=0の場合、i

  • j

    • （jを1増やします）

• bのサイズがjと同じ場合はtrueを返します

• 関数getDuplicates（）を定義します。これには、配列strsが必要です。

• 訪問したセットと別のセットを定義する

• 初期化i：=0の場合、i

  • strs [i]が訪問中の場合、-

    • strs[i]をretに挿入します

  • strs[i]をvisitedに挿入します

• retを返す

• メインの方法から、次のようにします-

• 文字列の長さに基づいて配列strsを並べ替えます

• 1セットの重複を定義します：=getDuplicates（strs）

• 初期化i：=0の場合、i

  • strs [i]が重複している場合、-

    • 次の部分を無視し、次の反復にスキップします

  • iが0と同じ場合、-

    • strs [i]

      の戻りサイズ

  • 初期化j：=0の場合、j

    • isSubsequence（strs [j]、strs [i]）がfalseの場合、-

      • 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