leetcode

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 };