ลำดับย่อยที่ผิดปกติที่ยาวที่สุด II ใน C ++

สมมติว่าเรามีรายการสตริง เราต้องหาลำดับย่อยที่ไม่ธรรมดาที่ยาวที่สุดในหมู่พวกเขา ลำดับย่อยที่ไม่ธรรมดาที่ยาวที่สุดคือลำดับย่อยที่ยาวที่สุดของหนึ่งในสตริงเหล่านี้ และลำดับย่อยนี้ไม่ควรเป็นผลสืบเนื่องใดๆ ของสตริงอื่นๆ

เรารู้ว่าลำดับย่อยเป็นลำดับที่สามารถได้มาจากลำดับหนึ่งโดยการลบอักขระบางตัวโดยไม่เปลี่ยนลำดับขององค์ประกอบที่เหลือ

ในที่นี้เราจะรวบรวมรายการสตริง และผลลัพธ์ต้องเป็นความยาวของลำดับย่อยที่ไม่ธรรมดาที่ยาวที่สุด หากไม่มีลำดับย่อยที่ผิดปกติที่ยาวที่สุด ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น "aba", "cdc", "eae" ผลลัพธ์จะเป็น 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน isSubsequence() ซึ่งจะใช้ a, b,

• เจ :=0

• สำหรับการเริ่มต้น i :=0, เมื่อ i

  • ถ้า j <ขนาดของ b และ a[i] เท่ากับ b[j] แล้ว −

    • (เพิ่มขึ้น j โดย 1)

• คืนค่าจริงเมื่อขนาดของ b เท่ากับ j

• กำหนดฟังก์ชัน getDuplicates() ซึ่งจะใช้อาร์เรย์ strs

• กำหนดหนึ่งชุดที่เยี่ยมชมและอีกหนึ่งชุด ret

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของ strs ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ถ้า strs[i] ถูกเยี่ยมชม ดังนั้น −

    • ใส่ strs[i] ลงใน ret

  • ใส่ strs[i] เข้าไป

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังนี้ −

• จัดเรียงอาร์เรย์ strs ตามความยาวของสตริง

• กำหนดชุดที่ซ้ำกัน :=getDuplicates(strs)

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของ strs ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ถ้า strs[i] ซ้ำกัน −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ถ้าฉันเหมือนกับ 0 แล้ว −

    • ขนาดส่งคืนของ strs[i]

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า 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