JZX轻语：简
LeetCode 1247 - 交换字符使得字符串相同
发表于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