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.
1import
This Java DFS-based solution explores all connected components in the similarity graph. Upon visiting an unvisited node, the dfs function delves into all connected nodes, ensuring complete exploration of the component leading to a count of distinct groups.