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.
1def find(parent, x):
2 if parent[x] != x:
3 parent[x] = find(parent, parent[x])
4 return parent[x]
5
6
7def union(parent, x, y):
8 rootX = find(parent, x)
9 rootY = find(parent, y)
10 if rootX != rootY:
11 parent[rootY] = rootX
12
13
14def are_similar(a, b):
15 diff = 0
16 for i in range(len(a)):
17 if a[i] != b[i]:
18 diff += 1
19 if diff > 2:
20 return False
21 return diff == 2 or diff == 0
22
23
24def num_similar_groups(strs):
25 n = len(strs)
26 parent = list(range(n))
27
28 for i in range(n):
29 for j in range(i + 1, n):
30 if are_similar(strs[i], strs[j]):
31 union(parent, i, j)
32
33 return len(set(find(parent, i) for i in range(n)))
34
35
36# Example usage:
37strs = ["tars", "rats", "arts", "star"]
38print(num_similar_groups(strs))
39The Python implementation involves Union-Find operations for similarity checking and component grouping. The are_similar() function ensures at most two mismatches for a pair of similar strings. Union and path compression make set operations efficient.
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.