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 <vector>
#include <string>
using namespace std;
vector<int> parent;
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union_set(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootY] = rootX;
}
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;
}
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
parent.resize(n);
for (int i = 0; i < n; ++i) parent[i] = i;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (areSimilar(strs[i], strs[j])) {
union_set(i, j);
}
}
}
int count = 0;
for (int i = 0; i < n; ++i) {
if (find(i) == i) {
count++;
}
}
return count;
}
int main() {
vector<string> strs = {"tars", "rats", "arts", "star"};
cout << numSimilarGroups(strs) << endl;
return 0;
}
The C++ solution is similar to the C solution. It uses the Union-Find data structure with path compression to find and union sets in the list of strings. The areSimilar() function checks for similarity based on character mismatches in the strings.
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 <stdio.h>
2#include <stdbool.h>
3#include <string.h>
4#define MAX 300
5
6bool areSimilar(char* a, char* b) {
7 int diff = 0;
8 for (int i = 0; i < strlen(a); i++) {
9 if (a[i] != b[i]) {
10 diff++;
11 if (diff > 2) return false;
12 }
13 }
14 return diff == 2 || diff == 0;
15}
16
17void dfs(char **strs, int idx, int size, bool visited[]) {
18 visited[idx] = true;
19 for (int i = 0; i < size; i++) {
20 if (!visited[i] && areSimilar(strs[idx], strs[i])) {
21 dfs(strs, i, size, visited);
22 }
23 }
24}
25
26int numSimilarGroups(char **strs, int strsSize) {
27 bool visited[MAX] = {false};
28 int count = 0;
29
30 for (int i = 0; i < strsSize; i++) {
31 if (!visited[i]) {
32 dfs(strs, i, strsSize, visited);
33 count++;
34 }
35 }
36 return count;
37}
38
39int main() {
40 char *strs[] = {"tars", "rats", "arts", "star"};
41 int n = sizeof(strs) / sizeof(strs[0]);
42 printf("%d\n", numSimilarGroups(strs, n));
43 return 0;
44}
45This 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.