กลุ่มสตริงที่คล้ายกันใน C++

สมมติว่าเรามีสตริง X และ Y สองสตริง สิ่งเหล่านี้จะคล้ายคลึงกันหากเราสามารถสลับตัวอักษร X สองตัวได้ ดังนั้นมันจึงเท่ากับ Y นอกจากนี้ สตริง X และ Y สองสตริงจะคล้ายกันหากเท่ากัน ตัวอย่างเช่น ลองพิจารณา สองสตริงเป็นเหมือน "tars" และ "rats" คล้ายกัน หากเราสลับ t และ r เราจะพบสตริงอื่น ตอนนี้ "rats" และ "arts" คล้ายกัน แต่ "star" ไม่ใช่ คล้ายกับ "tars", "rats" หรือ "arts" ตอนนี้เราจะเห็นแล้วว่า กลุ่มเหล่านี้สร้างกลุ่มที่เชื่อมต่อกันสองกลุ่มด้วยความคล้ายคลึงกัน:{"tars", "rats", "arts"} และ {"star"} ที่นี่ "tars" และ "arts" อยู่ในกลุ่มเดียวกันแม้ว่าจะไม่เหมือนกันก็ตาม ดังนั้นแต่ละกลุ่มจึงเป็นคำที่อยู่ในกลุ่มก็ต่อเมื่อคำนั้นคล้ายกับคำอื่นในกลุ่มอย่างน้อยหนึ่งคำเท่านั้น สมมติว่าเรามีรายการ A ของสตริง ทุกสตริงใน A เป็นแอนนาแกรมของสตริงอื่น ๆ ใน A เราต้องค้นหาว่ามีกี่กลุ่ม?

ดังนั้น หากอินพุตเป็นเหมือน ["tars","rats","arts","star"] เอาต์พุตจะเป็น 2

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

• กำหนดพาเรนต์อาร์เรย์

• กำหนดอันดับอาร์เรย์

• กำหนดฟังก์ชัน getParent() ซึ่งจะใช้เวลา x

  • ถ้า parent[x] เหมือนกับ -1 แล้ว −

    • ผลตอบแทน x

  • ส่งคืนพาเรนต์[x] =getParent(พาเรนต์[x])

• กำหนดฟังก์ชัน unionn() ซึ่งจะใช้ x, y,

  • parX :=getParent(x), parY :=getParent(y)

  • ถ้า parX เหมือนกับ parY ดังนั้น −

    • คืนค่าเท็จ

  • ถ้า rank[parX]>=rank[parY] แล้ว −

    • อันดับ[parX] :=อันดับ[parX] + อันดับ[parY]

    • ผู้ปกครอง[parY] :=parX

  • มิฉะนั้น

    • อันดับ[parY] :=อันดับ[parY] + อันดับ[parX]

    • parent[parX] :=parY

  • คืนความจริง

• กำหนดฟังก์ชัน ok() ซึ่งจะใช้เวลา s1, s2,

  • cnt :=0

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

    • ถ้า s1[i] ไม่เท่ากับ s2[i] ดังนั้น −

      • (เพิ่มขึ้นอีก 1)

    • ถ้า cnt> 2 แล้ว −

      • คืนค่าเท็จ

  • คืนความจริง

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

• ยกเลิก :=0

• n :=ขนาดของ A

• ret :=n

• parent :=อาร์เรย์ขนาด n และเติมด้วย -1

• rank :=อาร์เรย์ขนาด n และเติมด้วย 1

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

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

    • ถ้า ok(A[i], A[j]) ไม่ใช่ศูนย์ ดังนั้น −

      • ถ้า unionn(i, j) ไม่ใช่ศูนย์ ดังนั้น −

        • (ลดหย่อน 1)

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> parent;
   vector<int> rank;
   int getParent(int x){
      if (parent[x] == -1)
      return x;
      return parent[x] = getParent(parent[x]);
   }
   bool unionn(int x, int y){
      int parX = getParent(x);
      int parY = getParent(y);
      if (parX == parY)
      return false;
      if (rank[parX] >= rank[parY]) {
         rank[parX] += rank[parY];
         parent[parY] = parX;
      } else {
         rank[parY] += rank[parX];
         parent[parX] = parY;
      }
      return true;
   }
   bool ok(string& s1, string& s2){
      int cnt = 0;
      for (int i = 0; i < s1.size(); i++) {
         if (s1[i] != s2[i])
         cnt++;
         if (cnt > 2)
         return false;
      }
      return true;
   }
   int numSimilarGroups(vector<string>& A){
      int ret = 0;
      int n = A.size();
      ret = n;
      parent = vector<int>(n, -1);
      rank = vector<int>(n, 1);
      for (int i = 0; i < n; i++) {
         for (int j = i + 1; j < n; j++) {
            if (ok(A[i], A[j])) {
               if (unionn(i, j))
               ret--;
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"tars","rats","arts","star"};
   cout << (ob.numSimilarGroups(v));
}

อินพุต

{"tars","rats","arts","star"}

ผลลัพธ์

2