我的博客

leetcode weekly 155 5199. 交换字符串中的元素 1202. Smallest String With Swaps

目录
  1. 解答

给你一个字符串 s,以及该字符串中的一些「索引对」数组 pairs,其中 pairs[i] = [a, b] 表示字符串中的两个索引(编号从 0 开始)。

你可以 任意多次交换pairs 中任意一对索引处的字符。

返回在经过若干次交换后,s 可以变成的按字典序最小的字符串。

示例 1:

1
2
3
4
5
输入:s = "dcab", pairs = [[0,3],[1,2]]
输出:"bacd"
解释:
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"

示例 2:

1
2
3
4
5
6
输入:s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出:"abcd"
解释:
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"

示例 3:

1
2
3
4
5
6
输入:s = "cba", pairs = [[0,1],[1,2]]
输出:"abc"
解释:
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"

提示:

  • 1 <= s.length <= 10^5
  • 0 <= pairs.length <= 10^5
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • s 中只含有小写英文字母

解答

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
class Solution:
def smallestStringWithSwaps(self, s: str, pairs) -> str:
fa = [i for i in range(len(s))]
def getfa(x):
if x == fa[x]:
return x
else:
fa[x] = getfa(fa[x])
return fa[x]
def merge(x, y):
if getfa(x) != getfa(y): fa[fa[x]] = fa[y]
for p in pairs: merge(*p)
mp1 = {}
mp2 = {}
for i in range(len(s)):
f = getfa(i)
if f not in mp1:
mp1[f] = []
mp2[f] = []
mp1[f].append(s[i])
mp2[f].append(i)
l = ['' for i in range(len(s))]
for k in mp1:
mp1[k].sort()
for i in range(len(mp1[k])):
l[mp2[k][i]] = mp1[k][i]
return ''.join(l)

评论无需登录,可以匿名,欢迎评论!