-
Notifications
You must be signed in to change notification settings - Fork 0
/
1202.smallest-string-with-swaps.cpp
66 lines (62 loc) · 1.44 KB
/
1202.smallest-string-with-swaps.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
* @lc app=leetcode id=1202 lang=cpp
*
* [1202] Smallest String With Swaps
*/
// @lc code=start
auto speedup = [](){
cin.tie(nullptr);
cout.tie(nullptr);
ios::sync_with_stdio(false);
return 0;
}();
struct UnionSet {
vector<int> parent;
public:
UnionSet(int size): parent(size) {
for(int i = 0; i < size; ++i) {
parent[i] = i;
}
}
int find(int x) {
if(parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void merge(int x, int y) {
x = find(x);
y = find(y);
parent[x] = y;
}
};
class Solution {
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int len = s.length();
UnionSet us(s.length());
for(const auto &pair : pairs) {
us.merge(pair[0], pair[1]);
}
unordered_map<int, vector<int>> indice;
unordered_map<int, string> chars;
for(int i = 0; i < len; ++i) {
int parent = us.find(i);
indice[parent].push_back(i);
chars[parent].push_back(s[i]);
}
for(auto &[parent, s] : chars) {
sort(s.begin(), s.end());
}
string answer(len, '\x00');
for(const auto &[parent, index]: indice) {
for(int i = 0; i < index.size(); ++i) {
answer[index[i]] = chars[parent][i];
}
}
return move(answer);
}
};
// Accepted
// 36/36 cases passed (176 ms)
// Your runtime beats 85.32 % of cpp submissions
// Your memory usage beats 73.82 % of cpp submissions (49.6 MB)
// @lc code=end