1202. 交换字符串中的元素 #

标签：深度优先搜索、广度优先搜索、并查集、哈希表、字符串
难度：中等

题目大意 #

给定一个字符串 s，再给定一个数组 pairs，其中 pairs[i] = [a, b] 表示字符串的第 a 个字符可以跟第 b 个字符交换。

只要满足 pairs 中的交换关系，可以任意多次交换字符串中的字符。

要求：返回 s 经过若干次交换之后，可以变成的字典序最小的字符串。

解题思路 #

如果第 a 个字符可以跟第 b 个字符交换，第 b 个字符可以跟第 c 个字符交换，那么第 a 个字符、第 b 个字符、第 c 个字符之间就可以相互交换。

我们使用并查集，将可以相互交换的位置放到同一个集合中。

然后再将同一个集合中字符进行逆序排序，然后遍历所有位置，弹出每个位置对应集合中末尾的字符，将其加入到答案数组中。

最后数组所构造的字符串即为答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


import collections

class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.count = n

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return

        self.parent[root_x] = root_y
        self.count -= 1

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        size = len(s)
        union_find = UnionFind(size)
        for pair in pairs:
            union_find.union(pair[0], pair[1])
        mp = collections.defaultdict(list)

        for i, ch in enumerate(s):
            mp[union_find.find(i)].append(ch)

        for vec in mp.values():
            vec.sort(reverse=True)

        ans = []
        for i in range(size):
            x = union_find.find(i)
            ans.append(mp[x][-1])
            mp[x].pop()

        return "".join(ans)