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，实现如下：
3.编写函数 Find(i int) int 实现路径压缩的查找操作，返回元素 i 所在集合的根节点，具体步骤如下：
4.编写函数 Union(i, j int) 实现按秩合并的操作，将元素 i 所在集合和元素 j 所在集合合并成一个集合，具体步骤如下：
5.编写函数 Sets0() int 返回当前并查集中集合的数量，直接返回结构体字段 Sets 的值即可。
6.编写函数 numSimilarGroups(strs []string) int，遍历每对字符串，如果它们属于不同的集合，判断它们是否相似，如果是相似的则将它们合并到同一个集合中，最终返回并查集中剩余的集合数量，具体步骤如下：
7.在 main 函数中，给定输入字符串列表 strs，调用 numSimilarGroups 函数计算相似字符串组的数量，并输出结果。
时间复杂度：在最坏情况下，需要枚举任意两个字符串进行比较，因此需要 O(n2m) 的时间复杂度，其中 n 是字符串数组 strs 中字符串的数量，m 是字符串的长度。并查集合并操作的时间复杂度为 α(n)，其中 α(n) 是反阿克曼函数的某个很小的值，可以看作是常数级别的时间复杂度，因此对总时间复杂度的贡献可以忽略不计。因此，最终的时间复杂度为 O(n2m)。
空间复杂度：主要由并查集所用的空间和额外的辅助变量所占用的空间构成。其中，并查集需要的空间是 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;}
复制代码
评论