交换字符串中的元素

难度: Medium

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

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

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

示例 1:

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

示例 2：

输入：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：

输入：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 中只含有小写英文字母

Submission

运行时间: 145 ms

内存: 39.3 MB

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        while self.parent[x] != 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 False
        self.parent[root_x] = root_y
        return True
    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 = defaultdict(list)
        
        for i, ch in enumerate(s):
            mp[union_find.find(i)].append(ch)
        
        for key, value in mp.items():
            value.sort(reverse=True)

        ans = []
        for i in range(size):
            ans.append(mp[union_find.find(i)].pop())
        
        return "".join(ans)

Explain

这个题解使用了并查集(Union-Find)数据结构来解决问题。首先，使用并查集将可以互相交换的字符分组。然后，将每个组内的字符按照字典序排序，以确保组内的字符排列是最小的。最后，重新构建字符串，确保每个位置的字符都是所在组内字典序最小的。

时间复杂度: O(m + nlogn)

空间复杂度: O(n)

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        while self.parent[x] != 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 False
        self.parent[root_x] = root_y
        return True
    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 = defaultdict(list)
        
        for i, ch in enumerate(s):
            mp[union_find.find(i)].append(ch)
        
        for key, value in mp.items():
            value.sort(reverse=True)

        ans = []
        for i in range(size):
            ans.append(mp[union_find.find(i)].pop())
        
        return \"\".join(ans)

Explore

在使用并查集处理多个连接组件的索引对时，我们通过`union`方法将每一对索引合并。对于每个索引对（例如`(i, j)`），我们首先找到各自的根节点（使用`find`方法），然后确定这两个根节点是否相同。如果不同，说明它们属于不同的组，此时将它们合并，通常是把一个根节点的父节点设置为另一个根节点，从而将两个组合并为一个组。这样，通过逐对处理所有给出的索引对，可以确保所有相关索引在并查集中正确地合并到相应的组中。

在处理每个组内的字符时选择对它们进行字典序排序的原因是确保在重构字符串时，每个位置能使用该组中字典序最小的字符。这种排序方式能够确保在每个可以互换的字符组内，字符都是按照字典序排列的最优方式。然而，虽然这可以保证局部最优（组内字符是最小的），但不一定是全局最优。全局最小的字典序需要考虑所有可能的字符置换，这通常需要更复杂的算法来确保。所以，这种方法在局部组内是最优的，但在全局可能不是最小的。

在并查集的`union`方法中，如果`root_x`等于`root_y`，这意味着两个索引已经在同一个连接组件中，即它们已经是通过某种方式直接或间接连接的。在这种情况下直接返回，是因为不需要进行任何操作就可以保持它们的连接状态。这种情况不会对最终的结果造成负面影响，因为它只是确认了这两个索引已经处于同一个组内，无需重复合并。

在最终重构字符串时使用`pop()`方法从列表中取出字符是为了从已排序的字符列表中选择当前最小的字符（因为在字典序排序后使用`pop()`可以从列表尾部取出最小元素）。这种方式是稳定的，因为每个组内的字符已经按照字典序进行了排序，因此每次使用`pop()`都确保从该组中取出当前可用的最小字符。这有助于确保每个位置的字符都是该位置可能的所有字符中字典序最小的，从而使得最终结果字符串尽可能小。