839相似字符串

cong12586 2021-01-31 原文

# 力扣已经连续好几天的题目都是考察并查集的题，
# 今天也不例外，是否为相似字符串组就表示一个组，也就是一个连通的区域
# 这道题变向是考察一共有多少个连通区域。
# 首先是并查集的魔板。
class DSU:
    def __init__(self,n):
        # 初始化一个数组，初始每个节点都不联通。
        self.father = list(range(n))
        # 这里定义一个数字，表示有连通区域的个数，
        # 初始的的时候都不连通，为n
        self.num = n
    def find(self,x):
        # 寻找父节点。
        if x != self.father[x]:
            # 这里已经向上循环，最后找到最上层的父亲节点，也就是x = self.father[x]那个。
            # 然后把他的儿子节点的父节点都定义为最上层那个。
            self.father[x] = self.find(self.father[x])
        return self.father[x]
    def union(self,x,y):
        # 判断是否连通，
        if not self.is_connected(x,y):
            # 进行连通，
            self.father[self.find(y)] = self.find(x)
            # 注意这里需要把连通区域的个数减去一。
            self.num -= 1
    # 判断是否为连通区域。
    def is_connected(self,x,y):
        return self.find(x) == self.find(y)

from typing import List
class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        # 判断字符串的长度。
        length = len(strs)
        if length <= 1:return length
        # 初始化一个并查集。
        dsu = DSU(length)
        # 双重遍历进行判断。
        for i in range(length):
            for j in range(i + 1,length):
                # 这里判断是否为相似字符串，如果是的话就将他们连通。
                if self.isSimila(strs[i],strs[j]):
                    # 首先应该先判断是否连通，这一步判断在union函数中做了，

                    dsu.union(i,j)
        return dsu.num
    # 判断是否为相似字符串函数，只需要统计字符串中不相同字符的个数是否为0或者2就好了。
    def isSimila(self,str1,str2):
        count = 0
        for i in range(len(str1)):
            if str1[i] != str2[i]:
                count += 1
        return count == 2 or count == 0