发表于 2024.07.14

• 需要一些观察和分析，首先，在同一个下标i下，如果s1[i]为x，而s2[i]为y，将其记为xy对；如果s1[i]为y，而s2[i]为x，将其记为yx对。那么，如果存在两个相同的xy对(或者两个相同的yx对)，那么可以通过一次交换将这两个对应的下标变为相同的字符；而如果仅有一个xy对以及一个yx对，那么需要两次交换才能将其变为相同的字符。对于整个字符串而言，如果xy对和yx对的个数总和为奇数，那么无法将其变为相同的字符串(不难证明，上述情况下，两个字符串的x个数为奇数，y个数，不可能能做到两个字符串相等)。如果为偶数，则存在可行解，且最优解可通过贪心的做法，尽量先同类对交换(只需要一次交换操作)(即xy对内部两两匹配，yx对内部两两匹配)，如果最后剩下一个xy对和一个yx对，那么需要两次交换。

  class Solution:
      def minimumSwap(self, s1: str, s2: str) -> int:
          xy_pair_cnt = yx_pair_cnt = 0
          for s1_ch, s2_ch in zip(s1, s2):
              if s1_ch != s2_ch:
                  if s1_ch == 'x':
                      xy_pair_cnt += 1
                  else:
                      yx_pair_cnt += 1
          if (xy_pair_cnt + yx_pair_cnt) % 2:
              return -1
          more, less = max(xy_pair_cnt, yx_pair_cnt), min(xy_pair_cnt, yx_pair_cnt)
          return more // 2 + less // 2 + more % 2 + less % 2

• LC 题目链接