1202. Smallest String With Swaps

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

Python

DFS

from collections import defaultdict


class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        chars = list(s)
        visited = set()

        edges = defaultdict(list)
        for source, dist in pairs:
            edges[source].append(dist)
            edges[dist].append(source)

        def dfs(node, result):
            if node not in edges:
                return

            result.append(node)

            dests = edges.pop(node)  # while loop end point
            for dest in dests:
                dfs(dest, result)

        while edges:
            node = next(iter(edges))  # Start from whatever node of edges

            # 1. Find all connected nodes which is on of the sub-graph
            connected_nodes = []
            dfs(node, connected_nodes)

            # 2. Get the origin values of all the nodes in sub-graph
            swapped_values = [s[i] for i in connected_nodes]

            # 3. Sort both of them, then the data in these lists will be the
            #    mini swapped values of the sub-graph
            connected_nodes.sort()
            swapped_values.sort()

            # 4. Update the value of sub-graph in place
            for i, new_value in enumerate(swapped_values):
                target_index = connected_nodes[i]
                chars[target_index] = new_value

        return ''.join(chars)