Today's Challenge

https://leetcode.com/problems/smallest-string-with-swaps

Smallest String With Swaps - LeetCode

DFS나 UnionFind+minHeap으로 풀면 되는 문제라고 한다.
DFS는 익숙한데 UnionFind는 뭔지 모름..

python에서도 dfs는 꽤 쉽게 구현이 되는걸 한 번 더 느낌.

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        from collections import defaultdict
        d = defaultdict(list)
        s = list(s)
        visited = [False for _ in range(len(s))]
        
        for src, dest in pairs:
            d[src].append(dest)
            d[dest].append(src)
        
        def dfs(s, i, chars, indices):
            if visited[i]:
                return
            chars.append(s[i])
            indices.append(i)
            visited[i] = True
            
            for neigh in d[i]:
                dfs(s, neigh, chars, indices)
                
        for i in range(len(s)):
            if not visited[i]:
                chars = []
                indices = []
                
                dfs(s, i, chars, indices)
                chars = sorted(chars)
                indices = sorted(indices)
                for c, i in zip(chars, indices):
                    s[i] = c       
        
        return ''.join(s)