leetcode

Solution to some Leetcode problems written in C++

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

0839.cpp (1251B)

0 class UnionFind { 1 int n, cnt = n; 2 vector<int> root, size; 3 4 public: 5 UnionFind(int n) : n(n), root(n), size(n, 1) { 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 (size[x] > size[y]) swap(x, y); 17 root[x] = y; 18 size[y] += size[x]; 19 cnt--; 20 } 21 } 22 23 int count() { return cnt; } 24 bool connected(int x, int y) { return find(x) == find(y); } 25 }; 26 27 class Solution { 28 bool similar(const string &s1, const string &s2) { 29 int diff = 0; 30 for (int i = 0; i < s1.size(); i++) { 31 if (s1[i] == s2[i]) continue; 32 if (diff < 2) 33 diff++; 34 else 35 return false; 36 } 37 return true; 38 } 39 40 public: 41 int numSimilarGroups(const vector<string> &strs) { 42 int n = strs.size(); 43 UnionFind uf(n); 44 for (int i = 0; i < n; i++) { 45 for (int j = i + 1; j < n; j++) { 46 if (similar(strs[i], strs[j])) uf.join(i, j); 47 } 48 } 49 return uf.count(); 50 } 51 };