Giả sử chúng ta có một chuỗi s và một mảng các cặp chỉ số pairs trong chuỗi, nơi pairs[i] = [a, b] chỉ ra 2 chỉ số (0-indexed) của chuỗi. Chúng ta có thể hoán đổi các ký tự tại bất kỳ cặp chỉ số nào trong pairs cho trước bất kỳ số lần nào. Chúng ta phải tìm chuỗi nhỏ nhất theo thứ tự từ điển mà s có thể biến đổi thành sau khi sử dụng các lần hoán đổi. Ví dụ, nếu s = "dcab" và pairs = [[0,3], [1,2]], đầu ra sẽ là "bacd". Hoán đổi s[0] và s[3], s = "bcad", sau đó hoán đổi s[1] và s[2], s = "bacd".
Để giải quyết, chúng ta làm theo các bước:
n := kích thước mảng, parent := mảng kích thước n, điền -1.
Tạo chuỗi ret kích thước n, điền '*'.
Với i từ 0 đến kích thước pairs:
u := pairs[i][0], v := pairs[i][1].
Nếu parent[u] == parent[v], bỏ qua.
parent[parent[u]] := parent[v].
Định nghĩa mảng arr1 kích thước n.
Với i từ 0 đến n-1: chèn s[i] vào arr1[parent[i]].
Với i từ 0 đến n-1: sắp xếp arr1[i] theo thứ tự giảm dần.
Với i từ 0 đến n-1:
ret[i] := phần tử cuối của arr1[parent[i]].
Xóa phần tử cuối khỏi arr1[parent[i]].
Ví dụ (C++)
Hãy xem 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"