题目如下:
You are given a string
s
, and an array of pairs of indices in the stringpairs
wherepairs[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.Example 1:
Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination:
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"
Explaination:
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"
Explaination:
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"Constraints:
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.
解题思路:可以用并查集把所有可以交换的下标分成若干个组,每个组里面的下标都是可以互相交换的,这样只需要把每个组中下标所对应的最小字符放到最小下标的位置,次小值放到次小下标的位置…最大值放到最大下标的位置,即可得到结果。
代码如下:
class Solution(object):
def smallestStringWithSwaps(self, s, pairs):
"""
:type s: str
:type pairs: List[List[int]]
:rtype: str
"""
parent = [i for i in range(len(s))]
def find(v):
if v == parent[v]:
return v
return find(parent[v])
def union(v1,v2):
p1 = find(v1)
p2 = find(v2)
if p1 > p2:
parent[p1] = p2
else:
parent[p2] = p1 for (i,j) in pairs:
union(i,j)
dic_val = {}
for i in range(len(parent)):
p = find(i)
parent[i] = p
dic_val[p] = dic_val.setdefault(p,'') + s[i] for key in dic_val.iterkeys():
dic_val[key] = ''.join(sorted(list(dic_val[key]))) res = ''
for i in parent:
res += dic_val[i][0]
dic_val[i] = dic_val[i][1:] return res