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

那么稱 X 和 Y 兩個字符串相似。如果這兩個字符串本身是相等的，那它們也是相似的。

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

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

總之，它們通過相似性形成了兩個關(guān)聯(lián)組：{"tars", "rats", "arts"} 和 {"star"}。

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

形式上，對每個組而言，要確定一個單詞在組中，只需要這個詞和該組中至少一個單詞相似。

給你一個字符串列表 strs。列表中的每個字符串都是 strs 中其它所有字符串的一個字母異位詞。

請問 strs 中有多少個相似字符串組？

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

輸出：2。

答案2023-05-23：

具體過程如下：

1.定義一個結(jié)構(gòu)體?UnionFind，包含以下字段：

• ??Father []int：每個元素的父節(jié)點；

• ??Size []int：每個子集的大??；

• ??Help []int：幫助數(shù)組；

• ??Sets int：集合數(shù)量。

2.編寫函數(shù)?NewUnionFind(n int) *UnionFind，創(chuàng)建一個新的并查集，需傳入元素數(shù)量?n，實現(xiàn)如下：

• ??創(chuàng)建一個?UnionFind?結(jié)構(gòu)體?uf，分別用?make?函數(shù)初始化父節(jié)點數(shù)組、子集大小數(shù)組和幫助數(shù)組，將集合數(shù)量?Sets?初始化為元素數(shù)量?n；

• ??遍歷每個元素，將其父節(jié)點初始化為自身，子集大小初始化為1。

• ??返回?uf。

3.編寫函數(shù)?Find(i int) int?實現(xiàn)路徑壓縮的查找操作，返回元素?i?所在集合的根節(jié)點，具體步驟如下：

• ??定義輔助變量?hi?為0；

• ??如果元素?i?的父節(jié)點不是它本身，將?i?加入幫助數(shù)組，將?i?更新為其父節(jié)點；

• ??當?i?的父節(jié)點等于它本身時，表明已經(jīng)到達集合的根節(jié)點，遍歷幫助數(shù)組，依次將這些元素的父節(jié)點更新為根節(jié)點；

• ??返回根節(jié)點。

4.編寫函數(shù)?Union(i, j int)?實現(xiàn)按秩合并的操作，將元素?i?所在集合和元素?j?所在集合合并成一個集合，具體步驟如下：

• ??分別查找元素?i?和元素?j?所在集合的根節(jié)點，如果它們所在的集合已經(jīng)相同，則不需要合并；

• ??否則，比較兩個集合的大小，將小的集合合并到大的集合中，并更新父節(jié)點和子集大小，同時將集合數(shù)量減1。

5.編寫函數(shù)?Sets0() int?返回當前并查集中集合的數(shù)量，直接返回結(jié)構(gòu)體字段?Sets?的值即可。

6.編寫函數(shù)?numSimilarGroups(strs []string) int，遍歷每對字符串，如果它們屬于不同的集合，判斷它們是否相似，如果是相似的則將它們合并到同一個集合中，最終返回并查集中剩余的集合數(shù)量，具體步驟如下：

• ??創(chuàng)建一個新的并查集?uf，元素數(shù)量為輸入字符串列表?strs?的長度；

• ??遍歷輸入字符串列表?strs，對于每一對字符串?s1?和?s2，判斷它們是否屬于同一個集合，如果不是，則比較它們是否相似，如果是相似的，則將它們所在集合合并；

• ??返回并查集中集合的數(shù)量。

7.在?main?函數(shù)中，給定輸入字符串列表?strs，調(diào)用?numSimilarGroups?函數(shù)計算相似字符串組的數(shù)量，并輸出結(jié)果。

時間復雜度：在最壞情況下，需要枚舉任意兩個字符串進行比較，因此需要 $O(n^2m)$ 的時間復雜度，其中 $n$ 是字符串數(shù)組 strs 中字符串的數(shù)量，$m$ 是字符串的長度。并查集合并操作的時間復雜度為 $\alpha(n)$，其中 $\alpha(n)$ 是反阿克曼函數(shù)的某個很小的值，可以看作是常數(shù)級別的時間復雜度，因此對總時間復雜度的貢獻可以忽略不計。因此，最終的時間復雜度為 $O(n^2m)$。

空間復雜度：主要由并查集所用的空間和額外的輔助變量所占用的空間構(gòu)成。其中，并查集需要的空間是 $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;
}


福大大架構(gòu)師每日一題

java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡，操作系統(tǒng)。

521篇原創(chuàng)內(nèi)容

公眾號