JZX轻语：简
LeetCode 1202 - 交换字符串中的元素
发表于2024年07月07日
一开始没啥思路，以为是贪心算法之类的。后面想了下可以用图来建模，将字符串的index视作为节点，如果某两个位置的字符可以交换，则将这两个位置的节点连接起来(如果a和b可以交换，b和c可以交换，则a和c可以交换，具有传递性，这和连通分量的特性一致)。由于连通分量里面对应的字符可通过交换排成任意的次序，因此，对于每个连通分量，将其内部的字符排序后，再按照index从小到大的顺序填回去即可。连通分量的维护(更新)自然而然地想到了并查集。
为什么说连通分量里面对应的字符可通过交换排成任意的次序呢？可考虑一个特定的排列s，类似于拓扑排序，我们先将入度为0的节点对应的位置填入相应的字符(即，如果某个入度为0的节点对应的位置为i，我们需要将字符s[i]从当前的位置移动到i上来)，通过一系列的交换将这个字符移动到i上，然后将这个节点删除(即固定住这个位置，不参与后续的交换操作)，继续处理入度为0的节点，直至所有节点都被处理完。这样，我们就可以将这个排列转换为s。
from collections import defaultdict
class UnionSet:
def __init__(self, n):
self.n = n
self.pa = list(range(n))
def find(self, x: int) -> int:
if self.pa[x] != x:
self.pa[x] = self.find(self.pa[x])
return self.pa[x]
def unite(self, x: int, y: int):
self.pa[self.find(x)] = self.find(y)
def components(self): # 返回各个连通分量里所有节点对应的index
tmp_dict = defaultdict(list)
for i in range(self.n):
tmp_dict[self.find(i)].append(i)
return tmp_dict.values()
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
# 首先进行并查集的合并操作
uset = UnionSet(len(s))
for x, y in pairs:
uset.unite(x, y)
ans = list(s)
for component in uset.components():
# 处理每个连通分量里的字符排列
sorted_char_list_in_component = sorted(s[i] for i in component)
for i, idx in enumerate(sorted(component)):
# i为排序后的字符当前处理的下标，idx从小到大处理连通分量里index
ans[idx] = sorted_char_list_in_component[i]
return ''.join(ans)