aboutsummaryrefslogtreecommitdiff
path: root/similar_string_group.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'similar_string_group.cpp')
-rw-r--r--similar_string_group.cpp63
1 files changed, 63 insertions, 0 deletions
diff --git a/similar_string_group.cpp b/similar_string_group.cpp
new file mode 100644
index 0000000..273df4f
--- /dev/null
+++ b/similar_string_group.cpp
@@ -0,0 +1,63 @@
+// 839. Similar String Groups
+#include "leetcode.h"
+
+/*
+ * two strings 'x' and 'y' are similar if we can swap two letters
+ * of 'x' so that it equals 'y'. also two strings 'x' and 'y' are
+ * given a list of 'strs' of strings where every string in 'strs'
+ * is an anagram of every other string in 'strs'. how many groups?
+ */
+
+class disjointSet {
+ vector<int> v;
+ int sz;
+
+public:
+ void make_set(int n) {
+ v.resize(n);
+ iota(v.begin(), v.end(), 0);
+ sz = n;
+ }
+ disjointSet(int n) { make_set(n); }
+ int find(int i) {
+ if (i != v[i])
+ v[i] = find(v[i]);
+ return v[i];
+ }
+ void join(int i, int j) {
+ int r_i = find(i), r_j = find(j);
+ if (r_i != r_j) {
+ v[r_i] = r_j;
+ sz--;
+ }
+ }
+ int size() { return sz; }
+};
+
+class Solution {
+ bool similar(string a, string b) {
+ int n = 0;
+ for (int i = 0; i < a.size(); i++)
+ if (a[i] != b[i] && ++n > 2)
+ return false;
+ return true;
+ }
+
+public:
+ int numSimilarGroups(vector<string> &strs) {
+ disjointSet ds(strs.size());
+ for (int i = 0; i < strs.size(); i++)
+ for (int j = i + 1; j < strs.size(); j++)
+ if (similar(strs[i], strs[j]))
+ ds.join(i, j);
+ return ds.size();
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<string> s1 = {"tars", "rats", "arts", "star"};
+ vector<string> s2 = {"omv", "ovm"};
+ printf("%d\n", obj.numSimilarGroups(s1));
+ printf("%d\n", obj.numSimilarGroups(s2));
+}