本文共 1395 字，大约阅读时间需要 4 分钟。

题目：（中等）

标签：并查集、深度优先搜索

解法一：

class DSU:    def __init__(self, n: int):        self._n = n        self._array = [i for i in range(n)]        self._size = [1] * n    def find(self, i: int) -> int:        if self._array[i] != i:            self._array[i] = self.find(self._array[i])        return self._array[i]    def union(self, i: int, j: int) -> bool:        i, j = self.find(i), self.find(j)        if i != j:            if i < j:                self._array[j] = i            else:                self._array[i] = j            return True        else:            return False    def is_connected(self, i: int, j: int) -> bool:        return self.find(i) == self.find(j)    @property    def group_num(self):        """计算连通分支数量"""        return len(set(self._array))    @property    def max_group_size(self):        """计算最大连通分支包含的数量"""        import collections        return max(collections.Counter(self._array).values())class Solution:    def smallestEquivalentString(self, a: str, b: str, s: str) -> str:        size1, size2 = len(a), len(s)        dsu = DSU(26)        for i in range(size1):            dsu.union(ord(a[i]) - 97, ord(b[i]) - 97)        ans = []        for i in range(size2):            ans.append(chr(dsu.find(ord(s[i]) - 97) + 97))        return "".join(ans)

转载地址：https://dataartist.blog.csdn.net/article/details/117185425 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！