JZX轻语：简
LeetCode 1061 - 按字典序排列最小的等效字符串
发表于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)