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
class Solution {
private bool AreSimilar(string a, string b) {
int diff = 0;
for (int i = 0; i < a.Length; i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 2) return false;
}
}
return diff == 2 || diff == 0;
}
private void Dfs(string[] strs, bool[] visited, int idx) {
visited[idx] = true;
for (int i = 0; i < strs.Length; i++) {
if (!visited[i] && AreSimilar(strs[idx], strs[i])) {
Dfs(strs, visited, i);
}
}
}
public int NumSimilarGroups(string[] strs) {
int n = strs.Length;
bool[] visited = new bool[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
Dfs(strs, visited, i);
count++;
}
}
return count;
}
static void Main() {
Solution s = new Solution();
string[] strs = {"tars", "rats", "arts", "star"};
Console.WriteLine(s.NumSimilarGroups(strs));
}
}
The C# implementation employs DFS to handle components in the graph formed by similar strings. AreSimilar function ensures valid swaps, and each unvisited node initiates a DFS call to register all reachable similar nodes marked using a boolean array.