leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1202.cpp (1042B)

0 class UnionFind { 1 vector<int> root, rank; 2 3 public: 4 UnionFind(int n) : root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); } 5 6 int find(int x) { 7 if (x == root[x]) return x; 8 return root[x] = find(root[x]); 9 } 10 11 void join(int x, int y) { 12 x = find(x), y = find(y); 13 14 if (x != y) { 15 if (rank[x] > rank[y]) swap(x, y); 16 root[y] = x; 17 rank[x] += x == y; 18 } 19 } 20 }; 21 22 class Solution { 23 public: 24 string smallestStringWithSwaps(string s, vector<vector<int>> &pairs) { 25 UnionFind uf(s.size()); 26 vector<vector<char>> vs(s.size()); 27 28 for (auto &p : pairs) 29 uf.join(p[0], p[1]); 30 31 for (int i = 0; i < s.size(); i++) 32 vs[uf.find(i)].push_back(s[i]); 33 34 for (auto &s : vs) 35 sort(s.rbegin(), s.rend()); 36 37 for (int i = 0; i < s.size(); i++) { 38 int index = uf.find(i); 39 s[i] = vs[index].back(); 40 vs[index].pop_back(); 41 } 42 return s; 43 } 44 };