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.
1import java.util.*;
2
3public class Solution {
4 private int find(int[] parent, int x) {
5 if (parent[x] != x) parent[x] = find(parent, parent[x]);
6 return parent[x];
7 }
8
9 private void union(int[] parent, int x, int y) {
10 int rootX = find(parent, x);
11 int rootY = find(parent, y);
12 parent[rootY] = rootX;
13 }
14
15 private boolean areSimilar(String a, String b) {
16 int diff = 0;
17 for (int i = 0; i < a.length(); i++) {
18 if (a.charAt(i) != b.charAt(i)) {
19 diff++;
20 if (diff > 2) return false;
21 }
22 }
23 return diff == 2 || diff == 0;
24 }
25
26 public int numSimilarGroups(String[] strs) {
27 int n = strs.length;
28 int[] parent = new int[n];
29 for (int i = 0; i < n; i++) parent[i] = i;
30
31 for (int i = 0; i < n; i++) {
32 for (int j = i + 1; j < n; j++) {
33 if (areSimilar(strs[i], strs[j])) {
34 union(parent, i, j);
35 }
36 }
37 }
38
39 int count = 0;
40 for (int i = 0; i < n; i++) {
41 if (find(parent, i) == i) count++;
42 }
43 return count;
44 }
45
46 public static void main(String[] args) {
47 Solution s = new Solution();
48 String[] strs = {"tars", "rats", "arts", "star"};
49 System.out.println(s.numSimilarGroups(strs));
50 }
51}
52This Java solution implements the Union-Find for connected components in the similarity graph. The union and find functions manage disjoint sets while areSimilar() checks if two strings can be made equal by swapping at most two distinct characters.
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.