这个题解使用并查集来解决相似字符串分组的问题。主要思路是：
1. 先对输入的字符串数组去重。
2. 根据输入规模选择两种不同的算法：
- 当字符串数量n大于字符串长度平方m^2时，使用O(N*M^2)的算法
- 否则使用O(N^2*M)的算法
3. O(N^2*M)算法通过两两比较字符串的相似性，对相似的字符串进行并查集合并操作
4. O(N*M^2)算法先生成每个字符串的所有通配形式，建立通配串到原字符串的映射，同时记录字符串之间的相似关系，最后对有相似关系的字符串进行并查集合并
5. 最后对并查集的根节点去重并输出集合的大小，即为相似字符串组的数量
时间复杂度: O(min(N^2*M, N*M^2))
空间复杂度: O(N) ~ O(N*M^2)
class Solution:
def numSimilarGroups(self, A: List[str]) -> int:
# 字符串去重，这个是题目给的坑
A = [*{*A}]
n, m = len(A), len(A[0])
# 并查集初始化
self.p = [*range(n)]
# 选择方案：当n>m^2时使用O(N*M^2)算法，否则使用O(N^2*M)算法
self.nmm(A) if n > m * m else self.nnm(A)
# 对并查集的根节点去重并输出集合大小
return len({*map(self.uni, self.p)})
# 并查集查询连接函数
def uni(self, x: int):
if x != self.p[x]:
self.p[x] = self.uni(self.p[x])
return self.p[x]
# O(N^2*M)算法
def nnm(self, A: List[str]):
n, m = len(A), len(A[0])
# 相似判定函数
def check(x, y):
t = 0
for i in range(m):
if x[i] != y[i]:
t += 1
if t > 2:
return False
return True
for i in range(n):
for j in range(i + 1, n):
# 遍历串的两两组合，然后并查集连接
pi, pj = self.uni(i), self.uni(j)
if pi != pj and check(A[i], A[j]):
self.p[pj] = pi
# O(N*M^2)算法
def nmm(self, A: List[str]):
n, m = len(A), len(A[0])
# 匹配字典
d = collections.defaultdict(list)
# 关系集合
e = set()
for i, w in enumerate(A):
for l in range(m):
for r in range(l + 1, m):
# 遍历每个串的两个位置，生成通配串
t_w = f'{w[: l]}.{w[l + 1: r]}.{w[r + 1: ]}'
if d[t_w]:
for j in d[t_w]:
# 生成串串关系
e |= {(i, j)}
d[t_w] += [i]
for i, j in e:
# 遍历关系集合，然后并查集连接
pi, pj = self.uni(i), self.uni(j)
if pi != pi:
self.p[pj] = pi