[1202] Smallest String With Swaps | LeetCode Medium

🔎 문제설명

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.

#한글 요약

영문 소문자 문자열과 (a, b) 형식의 일부 쌍이 있습니다. 

여기서 a와 b는 문자열의 인덱스입니다. 

우리의 목표는 인덱스 a와 b의 문자를 교환하여 사전학적으로 가장 작은 문자열을 찾는 것입니다.

최대 스왑 수에 대한 제한은 없습니다.

Example 1

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"

# Swap s[0] and s[3], s = "bcad"
# Swap s[1] and s[2], s = "bacd"

Example 2

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"

# Swap s[0] and s[3], s = "bcad"
# Swap s[0] and s[2], s = "acbd"
# Swap s[1] and s[2], s = "abcd"

Example 3

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"

# Swap s[0] and s[1], s = "bca"
# Swap s[1] and s[2], s = "bac"
# Swap s[0] and s[1], s = "abc"

제한사항

• 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.

---

위 이미지는 어떻게 연결된 컴포넌트에 노드를 바꿀 수 있는지를 보여줍니다.

문제를 풀기위해 솔루션을 4단계로 나눠보겠습니다.

1. 주어진 pair를 사용해서 그래프를 만듭니다.

2. 그래프에서 연결된 구성요소를 찾습니다.

3. 각 연결된 구성요소를 오름차순으로 정렬합니다.

4. 사전순으로 가장 작은 문자열을 출력합니다.

여기서 가장 어려운 점은 무한스왑을 통해 연결 컴포넌트에 속하는 문자들을 정렬하는 것입니다.

연결된 구성요소를 찾는데 사용되는 알고리즘으로 B/DFS, Union-Find가 일반적으로 사용된다고 합니다.

---

🧊 파이썬 코드

유니온파인드 알고리즘 방식입니다.

class Solution:
    def union(self, a, b):
        self.parent[self.find(a)] = self.find(b)
		
    def find(self, a):
        if self.parent[a] != a:
            self.parent[a] = self.find(self.parent[a])

        return self.parent[a]
        
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		# 1. Union-Find
        self.parent = list(range(len(s)))
        for a, b in pairs:
            self.union(a, b)

		# 2. Grouping
        group = defaultdict(lambda: ([], []))  
        for i, ch in enumerate(s):
            parent = self.find(i)
            group[parent][0].append(i)
            group[parent][1].append(ch)

		# 3. Sorting
        res = [''] * len(s)
        for ids, chars in group.values():
            ids.sort()
            chars.sort()
            for ch, i in zip(chars, ids):
                res[i] = ch
                
        return ''.join(res)