[LeetCode] 1202 | Smallest String With Swaps | Python

---

문제 링크: https://leetcode.com/problems/smallest-string-with-swaps/

---

문제

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

---

조건

• 1 <= s.length <= $10^5$
• 0 <= pairs.length <= $10^5$
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s only contains lower case English letters.

---

내 풀이

pairs를 이용해 어떤 위치의 글자들을 서로 바꿀 수 있는지 adj에 저장한다.

dfs를 이용해서 서로 연결된 것들을 nei에 저장하고, 알파벳 순서로 앞부터 정렬한다.

a = sorted(nei, key=lambda x: x[1])에는 알파벳을 순서대로 정렬할 것이고,

b = sorted(nei, key=lambda x: x[0])는 그 알파벳이 있는 위치들을 순서대로 정렬할 것이다.

(ex. badc에서 a, d, c가 서로 연결되어있다면 nei=[(1, 'a'), (2, 'd'), (3, 'c')]가 될 것이며, a=[(1, 'a'), (3, 'c'), (2, 'd')], b=[(1, 'a'), (2, 'd'), (3, 'c')]가 될 것이다. a에서 정렬된 순서대로 ans에 넣는데, 이 때 넣는 위치는 앞에서부터 넣어야 하므로 b에서 정렬한 인텍스에 넣는다.)

---

코드

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        self.s = s
        N = len(s)
        self.adj = [[] for _ in range(N)]
        for i, j in pairs:
            self.adj[i].append(j)
            self.adj[j].append(i)
            
        self.visited = [0] * N
        ans = [''] * N
        
        for i in range(N):
            if not self.visited[i]:
                nei = []
                self.dfs(i, nei)
            
                if not nei:
                    ans[i] = s[i]
                else:
                    a = sorted(nei, key=lambda x: x[1])
                    b = sorted(nei, key=lambda x: x[0])
                    
                    for i in range(len(nei)):
                        ans[b[i][0]] = a[i][1]
            
        return ''.join(ans)
            
                
    def dfs(self, i, nei):
        nei.append((i, self.s[i]))
        self.visited[i] = 1
        for j in self.adj[i]:
            if not self.visited[j]:
                self.dfs(j, nei)