题目概要

题目描述

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

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

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

输入描述

1
2
3
4
5
一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母

输出描述

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

测试样例

样例1: 输入-输出-解释

1
2
dcab
[[0,3],[1,2]]

1
bacd

1
2
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"

题目来源

LeetCode

Python代码

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
def find(a, x):
    if a[x] == x:
        return x
    else:
        a[x] = find(a, a[x])
        return a[x]


s = input()
swap = eval(input())
a = [i for i in range(len(s))]
for x, y in swap:
    a[find(a, y)] = find(a, a[x])
a = [find(a, b) for b in a]

linked = {}
for k, v in enumerate(a):
    if v in linked:
        linked[v].append(k)
    else:
        linked[v] = [k]

res = []
for v in linked.values():
    v.sort()
    t = [s[loc] for loc in v]
    t.sort()
    res += [(v[i], t[i]) for i in range(len(v))]
res.sort()
print(''.join([v for k, v in res]))