Leetcode 839. 相似字符串组【附并查集模板】

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]=x
            self.rootSizes[x]=1
    
    def find(self,x):
        root=x
        while root!=self.roots[root]:
            root=self.roots[root]
        while x!=root:
            temp=self.roots[x]
            self.roots[x]=root
            x=temp
        return root
    
    def 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]=yroot
                self.rootSizes[yroot]+=self.rootSizes[xroot]
            else:
                self.roots[yroot]=xroot
                self.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=0
            for a,b in zip(s1,s2):
                if a!=b:
                    notSameCnt+=1
                if notSameCnt>2:
                    return False
            return notSameCnt==2
        for i in range(length):
            for j in range(i+1,length):
                if checkSim(strs[i],strs[j]):
                    uf.union(strs[i],strs[j])
        result=0
        for key,val in uf.roots.items():
            if key==val:
                result+=1
        # print(result)
        return result

4.执行结果