2023-05-23：如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等， 那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。 例如，“tars“-环球关注

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)$。

package mainimport "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 := 0for 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 []intSize   []intSets   intHelp   []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] = iuf.Size[i] = 1}return uf}func (uf *UnionFind) Find(i int) int {hi := 0for i != uf.Father[i] {uf.Help[hi] = ihi++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] = fiuf.Size[fi] += uf.Size[fj]} else {uf.Father[fi] = fjuf.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)}

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) -> 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,    size: Vec,    help: Vec, // 添加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    }}

#include #include #include 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;}

#include #include using namespace std;class UnionFind {public:    vector father;    vector size;    vector 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& 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 strs = { "tars", "rats", "arts", "star" };    int res = numSimilarGroups(strs);    cout << res << endl;    return 0;}

标签：