1202. Smallest String With Swaps

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

Smallest String With Swaps - LeetCode

그래프로 생각해야 하는 문제

 

특징은 You can swap the characters at any pair of indices in the given pairs any number of times. 이다.

몇번이고 스왑이 가능하다.

 

dfs로 연결된 그래프를 찾은 다음에

맨 앞에 lexicographcally한 문자로 치환하는 과정이 필요하다.

 

 

class Solution(object):
    def smallestStringWithSwaps(self, s, pairs):
        """
        :type s: str
        :type pairs: List[List[int]]
        :rtype: str
        """
        
        def dfs(i):
            visited.add(i)
            tmp.append(s[i])
            idx.append(i)
            #print(i,"i")
            for j in d[i]:
                if j not in visited:
                    dfs(j)        
        
        lst = list(s)
        visited = set()
        d = [[] for _ in range(len(s))]
        for i, j in pairs:
            d[i].append(j)
            d[j].append(i)
        #print(d,"d")
        for i in range(len(s)):
            if i not in visited:
                tmp = []
                idx = []
                dfs(i)
                #print(tmp, idx,"CONNECTED", visited)
                sorted_tmp = sorted(tmp)
                sorted_idx = sorted(idx)
            
                for index in range(len(sorted_idx)):
                    lst[sorted_idx[index]] = sorted_tmp[index]
        #print(lst,"FINAL")
        return ''.join(lst)