839. 相似字符串组

Difficulty
Hard
Tags
并查集
URL
https://leetcode-cn.com/problems/similar-string-groups/
Star
如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？
示例 1：
输入：strs = ["tars","rats","arts","star"]
输出：2
示例 2：
输入：strs = ["omv","ovm"]
输出：1
提示：
  • 1 <= strs.length <= 300
  • 1 <= strs[i].length <= 300
  • strs[i] 只包含小写字母。
  • strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。

法1 并查集

思路
采用并查集，将相似的字符串进行union，然后统计有几个集合
题解
class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        uf = Unionfind(len(strs))
        for i in range(0, len(strs)):
            for j in range(i+1, len(strs)):
                if self.isSimilar(strs[i], strs[j]):
                    uf.union(i, j)

        res = 0
        temp = uf.parents
        for i in range(len(temp)):
            if temp[i] == i:
                res += 1

        return res

    def isSimilar(self, str1, str2):
        # 只要有 小于两个字母 不相同的 就是相似字符串
        count = 0
        for i in range(0, len(str1)):
            if str1[i] != str2[i]:
                count += 1
        return count <= 2

class Unionfind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            self.parents[root_x] = root_y