class Solution:

def find(self, parent, x):
if parent[x] != x:
return self.find(parent, parent[x])
return parent[x]
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
eq = [i for i in range(26)]
ans = ''
for p, q in zip(s1, s2):
p = ord(p) - ord('a')
q = ord(q) - ord('a')
x = self.find(eq, p)
y = self.find(eq, q)
if x < y:
eq[y] = x
elif x > y:
eq[x] = y
for i, z in enumerate(eq):
eq[i] = self.find(eq, i)
for r in baseStr:
r = ord(r) - ord('a')
ans += chr(ord('a')+eq[r])

return ans


어제는 술 약속 있어서 + 문제가 어려워서 탈주함

equivalence relation은 집합의 포함관계가 가장 중요한 예시고 여기엔 유니언 파인드지!


이번에 유니언 파인드를 파이썬으로 처음 구현해봤는데

C++에서는 find 값 리턴하면서 바로 배열에 반영이 가능했는데

파이썬은 그게 안 되니까 이렇게 추가로 find로 넣어줘야하네.. 귀찮다.