2023-05-23：如果交换字符串X 中的两个不同位置的字母使得它和字符串 Y 相等 那么称 X和Y 两个字符串相似

2023-05-23：如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，

那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)；

"rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。

总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。

注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。

形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。

请问 strs 中有多少个相似字符串组？

输入：strs = ["tars","rats","arts","star"]。

输出：2。

答案2023-05-23：

具体过程如下：

1.定义一个结构体 UnionFind，包含以下字段：

• Father []int：每个元素的父节点；

• Size []int：每个子集的大小；

• Help []int：帮助数组；

• Sets int：集合数量。

2.编写函数 NewUnionFind(n int) *UnionFind，创建一个新的并查集，需传入元素数量 n，实现如下：

• 创建一个 UnionFind 结构体 uf，分别用 make 函数初始化父节点数组、子集大小数组和帮助数组，将集合数量 Sets 初始化为元素数量 n；

• 遍历每个元素，将其父节点初始化为自身，子集大小初始化为1。

• 返回 uf。

3.编写函数 Find(i int) int 实现路径压缩的查找操作，返回元素 i 所在集合的根节点，具体步骤如下：

• 定义辅助变量 hi 为0；

• 如果元素 i 的父节点不是它本身，将 i 加入帮助数组，将 i 更新为其父节点；

• 当 i 的父节点等于它本身时，表明已经到达集合的根节点，遍历帮助数组，依次将这些元素的父节点更新为根节点；

• 返回根节点。

4.编写函数 Union(i, j int) 实现按秩合并的操作，将元素 i 所在集合和元素 j 所在集合合并成一个集合，具体步骤如下：

• 分别查找元素 i 和元素 j 所在集合的根节点，如果它们所在的集合已经相同，则不需要合并；

• 否则，比较两个集合的大小，将小的集合合并到大的集合中，并更新父节点和子集大小，同时将集合数量减1。

5.编写函数 Sets0() int 返回当前并查集中集合的数量，直接返回结构体字段 Sets 的值即可。

6.编写函数 numSimilarGroups(strs []string) int，遍历每个字符串，如果它们属于不同的集合，判断它们是否相似，如果是相似的则将它们合并到同一个集合中，最终返回并查集中剩余的集合数量，具体步骤如下：

• 创建一个新的并查集 uf，元素数量为输入字符串列表 strs 的长度；

• 遍历输入字符串列表 strs，对于每一对字符串 s1 和 s2，判断它们是否属于同一个集合，如果不是，则比较它们是否相似，如果是相似的，则将它们所在集合合并；

• 返回并查集中集合的数量。

7.在 main 函数中，给定输入字符串列表 strs，调用 numSimilarGroups 函数计算相似字符串组的数量，并输出结果。

时间复杂度：在最坏情况下，需要枚举任意两个字符串进行比较，因此需要 $O(n^2m)$ 的时间复杂度，其中 $n$ 是字符串数组 strs 中字符串的数量，$m$ 是字符串的长度。并查集合并操作的时间复杂度为 $\alpha(n)$，其中 $\alpha(n)$ 是反阿克曼函数的某个很小的值，可以看作是常数级别的时间复杂度，因此对总时间复杂度的贡献可以忽略不计。因此，最终的时间复杂度为 $O(n^2m)$。

空间复杂度：主要由并查集所用的空间和额外的辅助变量所占用的空间构成。其中，并查集需要的空间是 $O(n)$，辅助变量 Help 需要的空间也是 $O(n)$，因此总的空间复杂度为 $O(n)$。

go语言完整代码如下：

package main

import "fmt"

func numSimilarGroups(strs []string) int {

n, m := len(strs), len(strs[0])

uf := NewUnionFind(n)

for i := 0; i < n; i++ {

for j := i + 1; j < n; j++ {

if uf.Find(i) != uf.Find(j) {

diff := 0

for k := 0; k < m && diff < 3; k++ {

if strs[i][k] != strs[j][k] {

diff++

}

}

if diff == 0 || diff == 2 {

uf.Union(i, j)

}

}

}

}

return uf.Sets0()

}

type UnionFind struct {

Father []int

Size   []int

Sets   int

Help   []int

}

func NewUnionFind(n int) *UnionFind {

uf := &UnionFind{

Father: make([]int, n),

Size:   make([]int, n),

Help:   make([]int, n),

Sets:   n,

}

for i := 0; i < n; i++ {

uf.Father[i] = i

uf.Size[i] = 1

}

return uf

}

func (uf *UnionFind) Find(i int) int {

hi := 0

for i != uf.Father[i] {

uf.Help[hi] = i

hi++

i = uf.Father[i]

}

for hi > 0 {

hi--

uf.Father[uf.Help[hi]] = i

}

return i

}

func (uf *UnionFind) Union(i, j int) {

fi, fj := uf.Find(i), uf.Find(j)

if fi != fj {

if uf.Size[fi] >= uf.Size[fj] {

uf.Father[fj] = fi

uf.Size[fi] += uf.Size[fj]

} else {

uf.Father[fi] = fj

uf.Size[fj] += uf.Size[fi]

}

uf.Sets--

}

}

func (uf *UnionFind) Sets0() int {

return uf.Sets

}

func main() {

strs := []string{"tars", "rats", "arts", "star"}

res := numSimilarGroups(strs)

fmt.Println(res)

}

在这里插入图片描述