Sponsored
Sponsored
In this approach, we treat each string as a node in a graph. Two nodes are connected if the corresponding strings are similar. We use a Union-Find data structure to efficiently group the strings into connected components based on similarity.
Time Complexity: O(n^2 * k) where n is the number of strings and k is the average length of the strings.
Space Complexity: O(n), storing the parent array.
1#include <stdio.h>
2#include <string.h>
3
4#define MAX 300
5
6int parent[MAX];
7
8int find(int x) {
9 if (parent[x] != x) parent[x] = find(parent[x]);
10 return parent[x];
11}
12
13void union_set(int x, int y) {
14 int rootX = find(x);
15 int rootY = find(y);
16 if (rootX != rootY) parent[rootY] = rootX;
17}
18
19int areSimilar(char *a, char *b) {
20 int diff = 0;
21 for (int i = 0; i < strlen(a); i++) {
22 if (a[i] != b[i]) {
23 diff++;
24 if (diff > 2) return 0;
25 }
26 }
27 return diff == 2 || diff == 0;
28}
29
30int numSimilarGroups(char **strs, int strsSize) {
31 for (int i = 0; i < strsSize; i++) parent[i] = i;
32
33 for (int i = 0; i < strsSize; i++) {
34 for (int j = i + 1; j < strsSize; j++) {
35 if (areSimilar(strs[i], strs[j])) {
36 union_set(i, j);
37 }
38 }
39 }
40
41 int count = 0;
42 for (int i = 0; i < strsSize; i++) {
43 if (find(i) == i) {
44 count++;
45 }
46 }
47 return count;
48}
49This solution uses the Union-Find data structure to keep track of connected string groups. The areSimilar() function calculates string similarity by counting character mismatches. If a mismatch is found more than twice, the strings are not similar. The main function initializes the parents and processes connections through the union-find operations to count the disjoint sets.
This approach considers each string as a node and treats detecting similarities like exploring components in a graph. We use a depth-first search (DFS) algorithm to explore nodes. If two strings are similar, we explore all strings similar to this pair within a recursive call.
Time Complexity: O(n^2 * k) where n is the number of strings and k is the length of strings.
Space Complexity: O(n) to maintain the visited array.
1#
This C solution employs DFS to exhaustively search connected components formed by similar strings. We use a boolean array to track visited nodes and explore each group fully once a node from that group is encountered.