题目描述
思路解析动画文字版
记牢一句话:不匹配分 xy、yx 两类,同类两两一次换掉,最后落单的一对 xy 和 yx 要两次。下面每帧都在套它。
总览 · 两串对齐,计数清零：上面这排是把 s1 和 s2 对齐后摆出来的 8 个位置,每个格子竖线左边是 s1 的字符、右边是 s2 的字符。准备两个计数器,xy 记「s1 是 x、s2 是 y」的位置数,yx 记「s1 是 y、s2 是 x」的位置数,现在都清成 0。从第 0 位开始,一位一位往右看。
看第 0 位：看第 0 位:s1 这位是 "x",s2 这位是 "y"。两个字符不一样,得分个类。
第 0 位 · 归入 xy 类：这位 s1 是 "x"、s2 是 "y",属于 xy 类,标成绿色,xy 计数加一,现在 xy = 1。
看第 1 位：看第 1 位:s1 这位是 "x",s2 这位是 "x"。两个字符一样。
第 1 位 · 相同,跳过：这位 s1 和 s2 都是 "x",本来就一样,不用动它,标成蓝色跳过,计数都不变。
看第 2 位：看第 2 位:s1 这位是 "y",s2 这位是 "x"。两个字符不一样,得分个类。
第 2 位 · 归入 yx 类：这位 s1 是 "y"、s2 是 "x",属于 yx 类,标成红色,yx 计数加一,现在 yx = 1。
看第 3 位：看第 3 位:s1 这位是 "x",s2 这位是 "y"。两个字符不一样,得分个类。
第 3 位 · 归入 xy 类：这位 s1 是 "x"、s2 是 "y",属于 xy 类,标成绿色,xy 计数加一,现在 xy = 2。
看第 4 位：看第 4 位:s1 这位是 "y",s2 这位是 "x"。两个字符不一样,得分个类。
第 4 位 · 归入 yx 类：这位 s1 是 "y"、s2 是 "x",属于 yx 类,标成红色,yx 计数加一,现在 yx = 2。
看第 5 位：看第 5 位:s1 这位是 "x",s2 这位是 "x"。两个字符一样。
第 5 位 · 相同,跳过：这位 s1 和 s2 都是 "x",本来就一样,不用动它,标成蓝色跳过,计数都不变。
看第 6 位：看第 6 位:s1 这位是 "x",s2 这位是 "y"。两个字符不一样,得分个类。
第 6 位 · 归入 xy 类：这位 s1 是 "x"、s2 是 "y",属于 xy 类,标成绿色,xy 计数加一,现在 xy = 3。
看第 7 位：看第 7 位:s1 这位是 "y",s2 这位是 "x"。两个字符不一样,得分个类。
第 7 位 · 归入 yx 类：这位 s1 是 "y"、s2 是 "x",属于 yx 类,标成红色,yx 计数加一,现在 yx = 3。
扫描完成 · 统计两类数量：8 个位置全看完:绿色 xy 类有 3 个(第 0、3、6 位),红色 yx 类有 3 个(第 2、4、7 位),蓝色相同位跳过 2 个。不匹配合计 6 个,是偶数,说明能配平、有解。下面开始配对算次数。
配对 · xy 类配出一对：先看绿色 xy 类。第 0 位和第 3 位都是「s1 是 x、s2 是 y」。把 s1 第 0 位的 "x" 和 s2 第 3 位的 "y" 对调一次,这两位就同时对齐了。两个同类不匹配,一次交换全消掉,已用 1 次。
配对 · xy 类剩一个单的：xy 类一共 3 个,两两配走一对,还剩第 6 位这一个 xy 落单,先放着,等会儿和落单的 yx 一起处理。
配对 · yx 类配出一对：再看红色 yx 类。第 2 位和第 4 位都是「s1 是 y、s2 是 x」,同样一次交换就能把这两位一起摆平,累计已用 2 次。
配对 · yx 类剩一个单的：yx 类也是 3 个,配走一对后剩第 7 位这一个 yx 落单。现在台面上剩一个 xy(第 6 位)和一个 yx(第 7 位)。
配对 · 跨类的一对要两次：落单这一个 xy 和一个 yx 不同类,不能一次解决。得先花一次交换把其中一个变成和另一个同类(比如把它俩先弄成两个 yx),再花一次消掉,这一对总共 2 次。加上前面两次,累计 4 次。
完成 · 答案 4 次：汇总:xy 类 3 个出 1 对、yx 类 3 个出 1 对,各 1 次;最后落单的 xy 加 yx 那一对 2 次。合起来 1 加 1 加 2 等于 4 次,跟开头说的答案对上了。
边界都一个套路:同类成对就一次,跨类落单一对就两次,不匹配总数为奇数直接 -1。
面试重点:同类一次、跨类两次的道理;奇数无解等价于 x 总数为奇;时间 O(n) 空间 O(1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minimumSwap(self, s1: str, s2: str) -> int: xy = yx = 0 for a, b in zip(s1, s2): xy += a < b yx += a > b if (xy + yx) % 2: return -1 return xy // 2 + yx // 2 + xy % 2 + yx % 2复杂度
- 时间：O(n)，n 为字符串长度。两串对齐后每个位置只比一次、记一次,整体是一遍线性扫描,最后做几下常数运算
- 空间：O(1)，自始至终只用 xy 和 yx 两个整数计数器,没有额外的数组或栈,峰值占用是常数,跟串多长无关
易错点
面试追问把动画讲成自己的话
追问为什么两个同类不匹配一次交换就够,而一个 xy 加一个 yx 要两次?
追问什么时候返回 -1,背后的道理是什么?
追问这题的时间和空间复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
用户分组
LeetCode 1282 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题