leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1061.cpp (735B)

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