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.
1function find(parent, x) {
2 if (parent[x] !== x) parent[x] = find(parent, parent[x]);
3 return parent[x];
4}
5
6function union(parent, x, y) {
7 const rootX = find(parent, x);
8 const rootY = find(parent, y);
9 if (rootX !== rootY) parent[rootY] = rootX;
10}
11
12function areSimilar(a, b) {
13 let diff = 0;
14 for (let i = 0; i < a.length; i++) {
15 if (a[i] !== b[i]) {
16 diff++;
17 if (diff > 2) return false;
18 }
19 }
20 return diff === 2 || diff === 0;
21}
22
23function numSimilarGroups(strs) {
24 const n = strs.length;
25 const parent = Array.from({ length: n }, (_, i) => i);
26
27 for (let i = 0; i < n; i++) {
28 for (let j = i + 1; j < n; j++) {
29 if (areSimilar(strs[i], strs[j])) {
30 union(parent, i, j);
31 }
32 }
33 }
34
35 const groups = new Set();
36 for (let i = 0; i < n; i++) {
37 groups.add(find(parent, i));
38 }
39
40 return groups.size;
41}
42
43// Example usage:
44const strs = ["tars", "rats", "arts", "star"];
45console.log(numSimilarGroups(strs));
46This JavaScript solution employs the Union-Find technique to group strings based on similarity criteria. Strings that differ by two characters or less can be merged into the same group. The function areSimilar() assists in determining if two strings are similar.
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
Python uses a recursion-based DFS to explore connected nodes starting from any node. The dfs function continually marks all reachable similar strings using a boolean array until complete exploration is achieved, allowing us to count each group accurately.