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.
1using System;
2
3class 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 if (rootX != rootY) parent[rootY] = rootX;
13 }
14
15 private bool AreSimilar(string a, string b) {
16 int diff = 0;
17 for (int i = 0; i < a.Length; i++) {
18 if (a[i] != b[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++) {
30 parent[i] = i;
31 }
32
33 for (int i = 0; i < n; i++) {
34 for (int j = i + 1; j < n; j++) {
35 if (AreSimilar(strs[i], strs[j])) {
36 Union(parent, i, j);
37 }
38 }
39 }
40
41 int count = 0;
42 for (int i = 0; i < n; i++) {
43 if (Find(parent, i) == i) count++;
44 }
45 return count;
46 }
47
48 static void Main() {
49 Solution s = new Solution();
50 string[] strs = {"tars", "rats", "arts", "star"};
51 Console.WriteLine(s.NumSimilarGroups(strs));
52 }
53}
54The C# code uses Union-Find with the path compression technique for optimal performance. The AreSimilar() function ensures that two strings can be in the same group if they allow for only two mismatches, thus allowing swapping to form similarity.
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
This 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.