发表于 2024.06.11

• 题目有点绕，但由于等价关系具有对称性和传递性(即a等价于b，b等价于c，则a等价于c)，因此可以使用集合来表示等价关系(即上述的a、b和c可以放在一个集合内)，而此类问题的解法通常是使用并查集。对于每个集合，我们需要找到集合内最小的字符，可适当修改下并查集的模板实现：每个集合的代表(即根节点)使用最小字符，在合并两个集合时，取两个集合内最小的字符作为合并后集合的最小字符。

  import string
  
  
  class UnionSet:
      def __init__(self):
          self.pa = {ch: ch for ch in string.ascii_lowercase}  # type: dict[str, str]
  
      def find(self, ch: str) -> str:
          if self.pa[ch] != ch:
              self.pa[ch] = self.find(self.pa[ch])
          return self.pa[ch]
  
      def unite(self, x: str, y: str):
          px = self.find(x)
          py = self.find(y)
          # 保证合并后的集合的根是最小字符
          if px < py:
              self.pa[py] = px
          else:
              self.pa[px] = py
  
  
  class Solution:
      def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
          uset = UnionSet()
          for c1, c2 in zip(s1, s2):
              uset.unite(c1, c2)
          ans = []
          for ch in baseStr:
              ans.append(uset.find(ch))
          return ''.join(ans)

• LC 题目链接