JZX轻语：简
LeetCode 1061 - 按列翻转得到最大值等行数
发表于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)