LeetCode 1247. 交换字符使得字符串相同
题目描述
题意分析
两个等长字符串只含
x和y。每次必须从两个不同字符串中各选一个字符交换，所选下标可以相同，也可以不同，目标是让两串逐位置完全一致。求最少交换次数，无法做到时返回
-1。不能在同一个字符串内部交换，也不是让两串各自排成某个固定顺序；最终相同的内容可以由交换结果决定。
解法：统计错位对数
核心思路
[!blue]
原本相同的位置可以保留，只统计两种错位：
xy表示第一串是x、第二串是y，yx则相反。两个同型错位之间进行一次跨串交换，可以同时修复这两个位置，所以每种类型先两两配对，每对只需一次。能否有解取决于总错位数的奇偶。两串合起来的
x总数在交换中不变；一个匹配位置贡献零个或两个x，每个错位恰好贡献一个。最终两串一致时x总数必为偶数，因此错位数为奇数就不可能全部修好。总错位数为偶数时，两类计数同为偶数，或者同为奇数。前一种可以完全用同型配对解决；后一种各剩一个异型错位。先在其中一个位置跨串交换，把它翻转为另一类型，再用一次同型交换修复两处，总共需要两次。
这也是最少次数：一次交换最多修好两个位置。同为偶数时已经达到这个下界；同为奇数时，若每步都修好两个，就只能不断消去同型对，无法消掉各剩一个的异型。因此至少还需一步不减少错位总数的类型调整，上述两步正好达到下界。
答案于是为
xy / 2 + yx / 2 + 2 * (xy % 2)，前提是已排除总错位数为奇数的情况。只统计类型便能求出最优数量，无需实际修改字符串。
解题步骤
- 同时扫描两串，相同位置跳过，分别累加
xy与yx错位数。- 两类数量之和为奇数时返回
-1。- 每类完整的两两配对贡献其数量整除二次交换。
- 若两类都为奇数，再加两次处理最后一对异型错位。
- 返回合计次数；没有错位时自然返回零。
代码实现
class Solution {
public int minimumSwap(String s1, String s2) {
int xy = 0;
int yx = 0;
for (int i = 0; i < s1.length(); i++) {
char a = s1.charAt(i);
char b = s2.charAt(i);
// 相同位置不产生错位，只统计 xy 和 yx 两种类型。
if (a == b) {
continue;
}
if (a == 'x') {
xy++;
} else {
yx++;
}
}
// 总错位数奇偶性保持不变，奇数无法变成全匹配。
if ((xy + yx) % 2 == 1) {
return -1;
}
// 同型每两项一次；双奇数时剩余一对异型需两次。
return xy / 2 + yx / 2 + (xy % 2) * 2;
}
}
func minimumSwap(s1 string, s2 string) int {
xy := 0
yx := 0
for i := 0; i < len(s1); i++ {
// 相同位置不产生错位，只统计 xy 和 yx 两种类型。
if s1[i] == s2[i] {
continue
}
if s1[i] == 'x' {
xy++
} else {
yx++
}
}
// 总错位数奇偶性保持不变，奇数无法变成全匹配。
if (xy+yx)%2 == 1 {
return -1
}
// 同型每两项一次；双奇数时剩余一对异型需两次。
return xy/2 + yx/2 + (xy%2)*2
}
复杂度分析
- 时间复杂度：$O(n)$，扫描每个位置一次，然后用计数直接计算答案。
- 空间复杂度：$O(1)$，只保存两类错位数量。
关键点总结
[!green]
- 两类错位完整描述待修复状态，同型配对一次修两处。
- 字符总数不变给出奇偶性限制，总错位为奇数时无解。
- 双奇数残余需要先翻转类型，再同型配对，额外代价不可省略。
- 构造达到修复数量下界，才能说明公式给出最少交换数。
易错点总结
[!yellow]
- 任意一种类型为奇数就返回无解，漏掉两类同为奇数但可用两步收尾的情况。
- 直接返回总错位数的一半，没有计算异型残余所需的额外一次调整。
- 将匹配位置也加入两类计数，凭空增加了需要修复的错位。
- 用同一串内部交换来论证一步完成，违反跨字符串交换的限制。
- 先把计数整除后再判断奇偶，原始余数已经丢失，应始终使用原计数计算残余。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 859. 亲密字符串 | 简单 | 原题只在第一串交换一次，本题可做多次跨串交换，不能只按两个失配位置判断。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！