สตริงที่เล็กที่สุดที่มีการสลับใน C ++

สมมติว่าเราได้ให้สตริง s และอาร์เรย์ของคู่ดัชนีในคู่สตริง โดยที่ pairs[i] =[a, b] หมายถึง 2 ดัชนี(0-indexed) ของสตริง เราสามารถสลับอักขระที่คู่ของดัชนีใด ๆ ในคู่ที่กำหนดจำนวนครั้งตามที่เราต้องการ เราต้องหาสตริงที่เล็กที่สุดเกี่ยวกับพจนานุกรมที่สามารถเปลี่ยนเป็นหลังจากใช้การสลับ ดังนั้นหากอินพุตเป็นเหมือน s =“dcab” และคู่ =[[0,3], [1,2]] เอาต์พุตจะเป็น “bacd” แลกเปลี่ยน s[0] และ s[3], s ="bcad" จากนั้นแลกเปลี่ยน s[1] และ s[2], s ="bacd"

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

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

• สร้างสตริงที่เรียกว่า ret ของ size n แล้วเติมด้วย *

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของคู่

  • u :=pairs[i, 0] and v :=pairs[i, 1]

  • ถ้า parent ของ u เหมือนกับ parent ของ v ให้ข้ามไปที่การวนซ้ำถัดไป

  • parent[parent of u] :=parent ของ v

• กำหนดอาร์เรย์ arr1 ขนาด n

• สำหรับฉันในช่วง 0 ถึง n – 1:ใส่ s[i] ลงใน arr[พาเรนต์ของ i]

• สำหรับฉันในช่วง 0 ถึง n – 1:sort arr[i] โดยการอ่านค่าจากด้านขวา

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1 −

  • ret[i] :=รายการสุดท้ายของ arr1[parent of i]

  • ลบโหนดสุดท้ายออกจาก arr1[parent of i]

ตัวอย่าง (C++)

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

class Solution {
public:
   vector <int> parent;
   int getParent(int x){
      if(parent[x] == -1) return x;
      return parent[x] = getParent(parent[x]);
   }
   string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
      int n = s.size();
      parent = vector <int>(n, -1);
      string ret(n, '*');
      for(int i = 0; i < pairs.size(); i++){
         int u = pairs[i][0];
         int v = pairs[i][1];
         if(getParent(u) == getParent(v)) continue;
         parent[getParent(u)] = getParent(v);
      }
      vector < char > arr1[n];
      for(int i = 0; i < n; i++){
         arr1[getParent(i)].push_back(s[i]);
      }
      for(int i = 0; i < n; i++){
         sort(arr1[i].rbegin(), arr1[i].rend());
      }
      for(int i = 0; i < n; i++){
         ret[i] = arr1[getParent(i)].back();
         arr1[getParent(i)].pop_back();
      }
      return ret;
   }
};

อินพุต

"dcab"
[[0,3],[1,2]]

ผลลัพธ์

"bacd"