1202. 交换字符串中的元素(Medium)

题目描述

给定一个字符串s 和 一些索引对 pairs，可以 任意多次交换 在 pairs 中任意一对索引处的字符。 问经过交换后，求出 s 可以变成的最小字典序的字符串。

样例

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
解释: 
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"

题目解析

使用 并查集 将所有可以交换的索引合并成一堆，如题目中， [[0,3],[1,2]] 可以将所有的索引分成两堆，一堆是 0,3 组成的 db ，另一堆是 1, 2 组成的 ca。然后分别排序，就变成了bd 和 ca。最后再按照原有的排序合并成 bacd。

代码

import collections
class DisJoinSetUnion:
    def __init__(self, n):
        self.father = list(range(n)) # 初始的时候，每个节点的父节点就是自己

    def find(self, x):
        if self.father[x] == x: # 终止条件是遇到了父节点
            return x
        self.father[x] = self.find(self.father[x])
        return self.father[x]

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        if fx == fy: # 两个节点是一个群的，就不用合并了
            return
        self.father[fy] = fx

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        djs = DisJoinSetUnion(n)
        for x, y in pairs:
           djs.union(x, y)

        mp = collections.defaultdict(list)
        for i in range(n):
           mp[djs.find(i)].append(s[i])
        for _, v in mp.items(): # 排序
            v.sort()

        ans = ""
        for i in range(n):
            father = djs.find(i) # 找到每个索引的
            ans += mp[father].pop(0) # 每个集合的第一个是最小的
        return ans