스왑이 있는 가장 작은 문자열

문자열 s 및 문자열 pairs의 인덱스 쌍 배열이 제공됩니다. 여기서 pairs[i] = [a, b]는 문자열의 인덱스 2개(인덱스 0)를 나타냅니다.

지정된 인덱스 쌍pairs에서 문자를 여러 번 바꿀 수 있습니다.

스왑을 사용한 후 변경할 수 있는 사전순으로 가장 작은 문자열s을 반환합니다.

예 1:

입력: s = "dcab", 쌍 = [[0,3],[1,2]]
출력: "bacd"
설명:
s[0] 및 s[3] 교체, s = "bcad"
s[1] 및 s[2] 교체, s = "bacd"

예 2:

입력: s = "dcab", 쌍 = [[0,3],[1,2],[0,2]]
출력: "abcd"
설명:
s[0] 및 s[3] 교체, s = "bcad"
s[0]과 s[2]를 바꿉니다. s = "acbd"
s[1]과 s[2]를 바꿉니다. s = "abcd"

예 3:

입력: s = "cba", 쌍 = [[0,1],[1,2]]
출력: "abc"
설명:
s[0]과 s[1]을 바꾸십시오. s = "bca"
s[1] 및 s[2] 교체, s = "bac"
s[0]과 s[1] 교환, s = "abc"

제약:

1 <= s.length <= 10^5

0 <= pairs.length <= 10^5

0 <= pairs[i][0], pairs[i][1] < s.length

s 영문 소문자만 포함합니다.

해결책:

from collections import defaultdict

class Solution:
    def dfs(self, graph, node, visited):
        for j in graph[node]:
            if j not in visited:
                visited.add(j)
                self.dfs(graph, j, visited)

    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        op = list(s)
        graph = defaultdict(list)
        for a, b in pairs:
            graph[a].append(b)
            graph[b].append(a)
        globalvisited = set()
        for x in graph:
            if x not in globalvisited:
                currvisited = {x}
                self.dfs(graph, x, currvisited)
                indexes = sorted(currvisited)
                indexes_asc = sorted(currvisited, key = lambda p: s[p])
                n = len(indexes)
                for i in range(n):
                    op[indexes[i]] = s[indexes_asc[i]]
                globalvisited.update(currvisited)
        return "".join(op)