- 标签:深度优先搜索、广度优先搜索、并查集、哈希表、字符串
- 难度:中等
题目大意
#
给定一个字符串 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)
|