Chuỗi nhỏ nhất có hoán đổi trong C ++

Giả sử chúng ta đã cho một chuỗi s và một mảng các cặp chỉ số trong các cặp chuỗi trong đó cặp [i] =[a, b] cho biết 2 chỉ số (được lập chỉ mục 0) của chuỗi. Chúng ta có thể hoán đổi các ký tự ở bất kỳ cặp chỉ số nào trong các cặp đã cho bất kỳ số lần nào tùy ý. Chúng ta phải tìm chuỗi nhỏ nhất về mặt từ vựng mà có thể thay đổi thành sau khi sử dụng hoán đổi. Vì vậy, nếu đầu vào giống như s =“dcab” và các cặp =[[0,3], [1,2]], thì đầu ra sẽ là “bacd”. Trao đổi s [0] và s [3], s ="bcad", sau đó trao đổi s [1] và s [2], s ="bacd".

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

• n:=kích thước của mảng, cha:=tạo một mảng có kích thước n và điền vào giá trị này bằng -1

• tạo một chuỗi được gọi là ret có kích thước n và điền vào chuỗi này với *

• cho tôi trong phạm vi từ 0 đến kích thước của các cặp

  • u:=cặp [i, 0] và v:=cặp [i, 1]

  • nếu cha của u giống với cha của v, thì hãy chuyển sang lần lặp tiếp theo

  • cha mẹ [cha mẹ của u]:=cha mẹ của v

• xác định một mảng arr1 có kích thước n

• cho tôi trong phạm vi 0 đến n - 1:chèn s [i] vào arr [cha của tôi]

• đối với tôi trong phạm vi từ 0 đến n - 1:sắp xếp arr [i] bằng cách đọc giá trị từ bên phải

• cho tôi trong phạm vi từ 0 đến n - 1 -

  • ret [i]:=mục nhập cuối cùng của arr1 [cha của tôi]

  • xóa nút cuối cùng khỏi arr1 [cha của tôi]

Ví dụ (C ++)

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

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

Đầu vào

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

Đầu ra

"bacd"