leetcode

Solution to some Leetcode problems written in C++

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

1061.cpp (735B)

0 class UnionFind { 1 int n, cnt = n; 2 vector<int> root; 3 4 public: 5 UnionFind(int n) : n(n), root(n) { iota(root.begin(), root.end(), 0); } 6 7 int find(int x) { 8 while (x != root[x]) 9 x = root[x] = root[root[x]]; 10 return x; 11 } 12 13 void join(int x, int y) { 14 x = find(x), y = find(y); 15 if (x != y) { 16 if (y > x) swap(x, y); 17 root[x] = y; 18 } 19 } 20 }; 21 22 class Solution { 23 public: 24 string smallestEquivalentString(string s1, string s2, string baseStr) { 25 UnionFind uf(126); 26 27 for (int i = 0; i < s1.size(); i++) 28 uf.join(s1[i], s2[i]); 29 30 for (char &c : baseStr) 31 c = uf.find(c); 32 return baseStr; 33 } 34 };