[LeetCode] 1061. Lexicographically Smallest Equivalent String

- Problem

1061. Lexicographically Smallest Equivalent String

- 내 풀이

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:

        def find(x):
            if x != parent[x]:
                x = find(parent[x])
            return x
        
        def union(x, y):
            x = find(x)
            y = find(y)
            if x < y:
                parent[y] = x
            else:
                parent[x] = y
        
        parent = {chr(x):chr(x) for x in range(97, 123)}        

        for c1, c2 in zip(s1, s2):
            if parent[c1] != parent[c2]:
                union(c1, c2)

        answer = "".join(find(c) for c in baseStr)

        return answer

- 결과

• 시간 복잡도: O(MN) (M: s1, s2의 길이, N: baseStr의 길이)
• 공간 복잡도: O(1)