leetcode

commit f75969e6c9cc596157aa5aca205ee7795a4a4c31
parent 504e4aa8a26d7d5a9d6e4a98138fb5a0f1e6da63
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 28 Apr 2023 10:20:19 +0200

Daily Problem

Diffstat:
A
Problems/0839.cpp
 | 
53
+++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 54 insertions(+), 0 deletions(-)
diff --git a/Problems/0839.cpp b/Problems/0839.cpp
@@ -0,0 +1,53 @@
+class UnionFind {
+  int n, cnt = n;
+  vector<int> root, size;
+
+public:
+  UnionFind(int n) : n(n), root(n), size(n, 1) {
+    iota(root.begin(), root.end(), 0);
+  }
+
+  int find(int x) {
+    while (x != root[x]) x = root[x] = root[root[x]];
+    return x;
+  }
+
+  void join(int x, int y) {
+    x = find(x), y = find(y);
+    if (x != y) {
+      if (size[x] > size[y]) swap(x, y);
+      root[x] = y;
+      size[y] += size[x];
+      cnt--;
+    }
+  }
+
+  int count() { return cnt; }
+  bool connected(int x, int y) { return find(x) == find(y); }
+};
+
+class Solution {
+  bool similar(const string &s1, const string &s2) {
+    int diff = 0;
+    for (int i = 0; i < s1.size(); i++) {
+      if (s1[i] == s2[i]) continue;
+      if (diff < 2)
+        diff++;
+      else
+        return false;
+    }
+    return true;
+  }
+
+public:
+  int numSimilarGroups(const vector<string> &strs) {
+    int n = strs.size();
+    UnionFind uf(n);
+    for (int i = 0; i < n; i++) {
+      for (int j = i + 1; j < n; j++) {
+        if (similar(strs[i], strs[j])) uf.join(i, j);
+      }
+    }
+    return uf.count();
+  }
+};
diff --git a/README.md b/README.md
@@ -343,6 +343,7 @@ for solving problems.
 |  0802  |   Medium   | [Find Eventual Safe States](Problems/0802.cpp)                                                   |
 |  0815  |    Hard    | [Bus Routes](Problems/0815.cpp)                                                                  |
 |  0830  |   Medium   | [Kth Smallest Element in a BST](Problems/0230.cpp)                                               |
+|  0839  |    Hard    | [Similar String Groups](Problems/0839.cpp)                                                       |
 |  0841  |   Medium   | [Keys and Rooms](Problems/0841.cpp)                                                              |
 |  0844  |    Easy    | [Backspace String Compare](Problems/0844.cpp)                                                    |
 |  0851  |   Medium   | [Loud and Rich](Problems/0851.cpp)                                                               |