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#include <vector>
#include <string>
using namespace std;
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;
}
void dfs(vector<string>& strs, vector<bool>& visited, int idx) {
visited[idx] = true;
for (int i = 0; i < strs.size(); ++i) {
if (!visited[i] && areSimilar(strs[idx], strs[i])) {
dfs(strs, visited, i);
}
}
}
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(strs, visited, i);
count++;
}
}
return count;
}
int main() {
vector<string> strs = {"tars", "rats", "arts", "star"};
cout << numSimilarGroups(strs) << endl;
return 0;
}
The C++ DFS solution iteratively examines each node (string) and explores all nodes connected directly or indirectly. areSimilar() ensures that we only traverse valid connections, creating distinct connected components for separate groups.