发表于 2024.06.11

• 不妨取个例子：如果通过多次列翻转后，数组[0, 0, 1]变为全0或者全1，那么通过相同的列翻转操作，数组[1, 1, 0](注意，110和011异或后为0)也可以变为全1或者全0，而其他排列的数组则不会变为全0或者全1(具有互斥性)。我们将这些两两异或后为0的行放在一个集合内，该问题本质就是求解最大的集合，其中集合内的行通过相同的列翻转操作可以变为全0或者全1。我们可以使用哈希表进行集合计数，而下一步就是如何表示这些集合：不难得知，每个集合内仅有两种可能的数字（如上述例子的001和100），其互为对方的反码，我们将有前导0的数字作为计数哈希表的键，而遇到前导1的数字时，我们将其反码作为键，这样就可以保证集合的唯一性。最后，我们只需要返回最大的集合的计数即可。

  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 题目链接