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)
}

rust完整代码如下：

fn main() {
    let strs = vec![
        "tars".to_string(),
        "rats".to_string(),
        "arts".to_string(),
        "star".to_string(),
    ];
    let res = num_similar_groups(strs);
    println!("{}", res);
}

fn num_similar_groups(strs: Vec<String>) -> i32 {
    let n = strs.len();
    let m = strs[0].len();
    let mut uf = UnionFind::new(n);
    for i in 0..n {
        for j in i + 1..n {
            // [i] [j]
            if uf.find(i) != uf.find(j) {
                let mut diff = 0;
                for k in 0..m {
                    if strs[i].as_bytes()[k] != strs[j].as_bytes()[k] {
                        diff += 1;
                    }
                    if diff >= 3 {
                        break;
                    }
                }
                if diff == 0 || diff == 2 {
                    uf.union(i, j);
                }
            }
        }
    }
    uf.sets() as i32
}

struct UnionFind {
    father: Vec<usize>,
    size: Vec<i32>,
    help: Vec<usize>, // 添加help字段
    sets: usize,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        let mut father = vec![0; n];
        let size = vec![1; n];
        for i in 0..n {
            father[i] = i;
        }
        Self {
            father,
            size,
            help: vec![0; n], // 初始化help
            sets: n,
        }
    }

    fn find(&mut self, i: usize) -> usize {
        let mut hi = 0;
        let mut j = i;
        while j != self.father[j] {
            self.help[hi] = j;
            hi += 1;
            j = self.father[j];
        }
        while hi > 0 {
            hi -= 1;
            self.father[self.help[hi]] = j;
        }
        j
    }

    fn union(&mut self, i: usize, j: usize) {
        let fi = self.find(i);
        let fj = self.find(j);
        if fi != fj {
            if self.size[fi] >= self.size[fj] {
                self.father[fj] = fi;
                self.size[fi] += self.size[fj];
            } else {
                self.father[fi] = fj;
                self.size[fj] += self.size[fi];
            }
            self.sets -= 1;
        }
    }

    fn sets(&self) -> usize {
        self.sets
    }
}

c语言完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* father;
    int* size;
    int* help;
    int sets;
} UnionFind;

UnionFind* newUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->father = (int*)malloc(sizeof(int) * n);
    uf->size = (int*)malloc(sizeof(int) * n);
    uf->help = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        uf->father[i] = i;
        uf->size[i] = 1;
    }
    uf->sets = n;
    return uf;
}

int find(UnionFind* uf, int i) {
    int hi = 0;
    while (i != uf->father[i]) {
        uf->help[hi++] = i;
        i = uf->father[i];
    }
    while (hi != 0) {
        hi--;
        uf->father[uf->help[hi]] = i;
    }
    return i;
}

void unionSet(UnionFind* uf, int i, int j) {
    int fi = find(uf, i);
    int fj = find(uf, 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--;
    }
}

int getSets(UnionFind* uf) {
    return uf->sets;
}

int numSimilarGroups(char** strs, int strsSize) {
    int n = strsSize, m = strlen(strs[0]);
    UnionFind* uf = newUnionFind(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (find(uf, i) != find(uf, j)) {
                int diff = 0;
                for (int k = 0; k < m && diff < 3; k++) {
                    if (strs[i][k] != strs[j][k]) {
                        diff++;
                    }
                }
                if (diff == 0 || diff == 2) {
                    unionSet(uf, i, j);
                }
            }
        }
    }
    return getSets(uf);
}

int main() {
    char* strs[] = { "tars", "rats", "arts", "star" };
    int strsSize = sizeof(strs) / sizeof(strs[0]);
    int res = numSimilarGroups(strs, strsSize);
    printf("%d\n", res); // 输出 2
    return 0;
}

c++完整代码如下：

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> father;
    vector<int> size;
    vector<int> help;
    int sets;

    UnionFind(int n) : father(n), size(n, 1), help(n), sets(n) {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    int find(int i) {
        int hi = 0;
        while (i != father[i]) {
            help[hi++] = i;
            i = father[i];
        }
        while (hi != 0) {
            father[help[--hi]] = i;
        }
        return i;
    }

    void unionSet(int i, int j) {
        int fi = find(i);
        int fj = find(j);
        if (fi != fj) {
            if (size[fi] >= size[fj]) {
                father[fj] = fi;
                size[fi] += size[fj];
            }
            else {
                father[fi] = fj;
                size[fj] += size[fi];
            }
            sets--;
        }
    }

    int getSets() {
        return sets;
    }
};

int numSimilarGroups(vector<string>& strs) {
    int n = strs.size(), m = strs[0].size();
    UnionFind uf(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (uf.find(i) != uf.find(j)) {
                int diff = 0;
                for (int k = 0; k < m && diff < 3; k++) {
                    if (strs[i][k] != strs[j][k]) {
                        diff++;
                    }
                }
                if (diff == 0 || diff == 2) {
                    uf.unionSet(i, j);
                }
            }
        }
    }
    return uf.getSets();
}

int main() {
    vector<string> strs = { "tars", "rats", "arts", "star" };
    int res = numSimilarGroups(strs);
    cout << res << endl;
    return 0;
}

本栏目推荐文章
• C++实现文件内查找字符串
• python字符串方法
• 【LeetCode 2701. 连续递增交易】MySQL用户变量编程得到严格递增连续子序列的开始位置，结束位置，长度等统计信息
• 字符串格式化
• SQL SERVER日期时间转字符串
• NC66 两个链表的第一个公共结点
• 希腊字母的读法和规范书写
• 字符串的拼接
• 每日一题 2024-1-13 构造限制重复的字符串
• 正则表达式复习二——元字符

字符串 字符 两个 字母 位置字符串 字母 字符 位置 字符串 字符 两个 字母 字符串 字母 字符438 字符串 字母 字符 字符 字符串 字母 空格 字符 字符串 字母 字典 字符串 字母 字符 模式 频次 字符串 字母 字符 字符 空格 中英 字母 字符串 字母 字符 数字