发表于 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)

• LC 题目链接