aboutsummaryrefslogtreecommitdiff
path: root/similar_string_group.c
diff options
context:
space:
mode:
Diffstat (limited to 'similar_string_group.c')
-rw-r--r--similar_string_group.c59
1 files changed, 59 insertions, 0 deletions
diff --git a/similar_string_group.c b/similar_string_group.c
new file mode 100644
index 0000000..b8ed3f9
--- /dev/null
+++ b/similar_string_group.c
@@ -0,0 +1,59 @@
+// 839. Similar String Groups
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.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?
+ */
+
+bool similar(char *a, char *b) {
+ int len = strlen(a), diff_count = 0;
+ for (int i = 0; i < strlen(a); i++) {
+ if (a[i] != b[i])
+ diff_count++;
+ if (diff_count > 2)
+ return false;
+ }
+ return true;
+}
+
+void dfs(char **a, int a_size, char *string) {
+ char *tmp = NULL;
+ for (int i = 0; i < a_size; i++) {
+ if (!a[i])
+ continue;
+ if (similar(a[i], string)) {
+ tmp = a[i];
+ a[i] = NULL;
+ dfs(a, a_size, tmp);
+ }
+ }
+}
+
+int numSimilarGroups(char **strs, int strs_size) {
+ int cnt = 0;
+ char *tmp = NULL;
+ if (!strs || strs_size)
+ return 0;
+ for (int i = 0; i < strs_size; i++) {
+ if (!strs[i])
+ continue;
+ tmp = strs[i];
+ strs[i] = NULL;
+ cnt++;
+ dfs(strs, strs_size, tmp);
+ }
+ return cnt;
+}
+
+int main() {
+ char s1[][4] = {{"tars"}, {"rats"}, {"arts"}, {"star"}};
+ char s2[][3] = {{"omv"}, {"ovm"}};
+ printf("%d\n", numSimilarGroups(s1, 4));
+ printf("%d\n", numSimilarGroups(s2, 2));
+}