1.题目基本信息
1.1.题目描述
如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。
例如，”tars” 和 “rats” 是相似的 (交换 0 与 2 的位置)； “rats” 和 “arts” 也是相似的，但是 “star” 不与 “tars”，”rats”，或 “arts” 相似。
总之，它们通过相似性形成了两个关联组：{“tars”, “rats”, “arts”} 和 {“star”}。注意，”tars” 和 “arts” 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？
1.2.题目地址
https://leetcode.cn/problems/similar-string-groups/description/
2.解题方法
2.1.解题思路
并查集
2.2.解题步骤
第一步，构建检测两个字符串是否相似的判断函数，实现该功能只需要统计俩字符串中不相等字符的个数，因为题目已经规定每个字符串的都是同一个字符串的异位词，如果不相等的字符个数等于2，则代表相似，反之，不相似。
第二步，构建并查集对象，并将所有字符串添加到并查集中，进行初始化。
第三步，遍历并查集的roots字典，获取构建的集合的个数（键值相等的键值对数即为集合个数），集合的个数即为题解。
3.解题代码
Python代码【带并查集模板】
class UninFind():def __init__(self):self.roots={}self.rootSizes={}def add(self,x):if x not in self.roots:self.roots[x]=xself.rootSizes[x]=1def find(self,x):root=xwhile root!=self.roots[root]:root=self.roots[root]while x!=root:temp=self.roots[x]self.roots[x]=rootx=tempreturn rootdef union(self,x,y):xroot,yroot=self.find(x),self.find(y)if xroot!=yroot:# 优化合并if self.rootSizes[xroot]<self.rootSizes[yroot]:self.roots[xroot]=yrootself.rootSizes[yroot]+=self.rootSizes[xroot]else:self.roots[yroot]=xrootself.rootSizes[xroot]+=self.rootSizes[yroot]class Solution:# 并查集# 第一步，构建检测两个字符串是否相似的判断函数，实现该功能只需要统计俩字符串中不相等字符的个数，因为题目已经规定每个字符串的都是同一个字符串的异位词，如果不相等的字符个数等于2，则代表相似，反之，不相似。# 第二步，构建并查集对象，并将所有字符串添加到并查集中，进行初始化。# 第三步，遍历并查集的roots字典，获取构建的集合的个数（键值相等的键值对数即为集合个数），集合的个数即为题解。def numSimilarGroups(self, strs: List[str]) -> int:length=len(strs)uf=UninFind()for str_ in strs:uf.add(str_)# 检查s1、s2是否相似def checkSim(s1,s2):notSameCnt=0for a,b in zip(s1,s2):if a!=b:notSameCnt+=1if notSameCnt>2:return Falsereturn notSameCnt==2for i in range(length):for j in range(i+1,length):if checkSim(strs[i],strs[j]):uf.union(strs[i],strs[j])result=0for key,val in uf.roots.items():if key==val:result+=1# print(result)return result
4.执行结果
