Chuỗi con II ít phổ biến nhất trong C ++

Giả sử chúng ta có một danh sách các chuỗi; chúng ta phải tìm ra dãy con dài nhất không phổ biến trong số chúng. Chuỗi con dài nhất không phổ biến thực sự là chuỗi con dài nhất của một trong những chuỗi này và chuỗi con này không được là bất kỳ chuỗi con nào của các chuỗi khác.

Chúng ta biết rằng dãy con là một dãy có thể bắt nguồn từ một dãy bằng cách xóa một số ký tự mà không làm thay đổi thứ tự của các phần tử còn lại.

Ở đây chúng ta sẽ lấy một danh sách các chuỗi và đầu ra cần phải là độ dài của dãy con dài nhất không phổ biến. Nếu không có dãy con dài nhất không phổ biến, thì trả về -1.

Vì vậy, nếu đầu vào là "aba", "cdc", "eae", thì đầu ra sẽ là 3

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm isSubsequence (), điều này sẽ nhận a, b,

• j:=0

• để khởi tạo i:=0, khi i

  • nếu j

    • (tăng j lên 1)

• trả về true khi kích thước của b giống với j

• Xác định một hàm getDuplicates (), điều này sẽ lấy một chuỗi mảng,

• Xác định một tập hợp đã truy cập và một tập hợp khác kiểm tra lại

• để khởi tạo i:=0, khi tôi

  • nếu strs [i] được truy cập, thì -

    • chèn strs [i] vào ret

  • chèn strs [i] vào đã truy cập

• trả lại ret

• Từ phương thức chính, thực hiện như sau -

• sắp xếp các chuỗi mảng dựa trên độ dài chuỗi

• Xác định một tập hợp các bản sao:=getDuplicates (strs)

• để khởi tạo i:=0, khi tôi

  • nếu strs [i] trùng lặp thì -

    • Bỏ qua phần sau, chuyển sang phần tiếp theo

  • nếu tôi giống 0, thì -

    • trả về kích thước của strs [i]

  • để khởi tạo j:=0, khi j

    • nếu isSubsequence (strs [j], strs [i]) là false, thì -

      • nếu j giống với i - 1, thì -

        • trả về kích thước của strs [i]

    • Nếu không

      • Ra khỏi vòng lặp

• trả về -1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

{"aba", "cdc", "eae"}

Đầu ra

3