交换字符使得字符串相同 图解题解

这道题到底在问什么

输入

s1 = "xx", s2 = "yy"

输出

1

输入

s1 = "xy", s2 = "yx"

输出

2

输入

s1 = "xx", s2 = "xy"

输出

-1

输入

本节演示 s1 = "xxyxyxxy", s2 = "yxxyxxyx"

输出

4

最优解：一步一步想明白

1. 3记牢一句话:不匹配分 xy、yx 两类,同类两两一次换掉,最后落单的一对 xy 和 yx 要两次。下面每帧都在套它。
2. 4上面这排是把 s1 和 s2 对齐后摆出来的 8 个位置,每个格子竖线左边是 s1 的字符、右边是 s2 的字符。准备两个计数器,xy 记「s1 是 x、s2 是 y」的位置数,yx 记「s1 是 y、s2 是 x」的位置数,现在都清成 0。从第 0 位开始,一位一位往右看。
3. 5看第 0 位:s1 这位是 "x",s2 这位是 "y"。两个字符不一样,得分个类。
4. 6这位 s1 是 "x"、s2 是 "y",属于 xy 类,标成绿色,xy 计数加一,现在 xy = 1。
5. 7看第 1 位:s1 这位是 "x",s2 这位是 "x"。两个字符一样。
6. 8这位 s1 和 s2 都是 "x",本来就一样,不用动它,标成蓝色跳过,计数都不变。
7. 9看第 2 位:s1 这位是 "y",s2 这位是 "x"。两个字符不一样,得分个类。
8. 10这位 s1 是 "y"、s2 是 "x",属于 yx 类,标成红色,yx 计数加一,现在 yx = 1。
9. 11看第 3 位:s1 这位是 "x",s2 这位是 "y"。两个字符不一样,得分个类。
10. 12这位 s1 是 "x"、s2 是 "y",属于 xy 类,标成绿色,xy 计数加一,现在 xy = 2。
11. 13看第 4 位:s1 这位是 "y",s2 这位是 "x"。两个字符不一样,得分个类。
12. 14这位 s1 是 "y"、s2 是 "x",属于 yx 类,标成红色,yx 计数加一,现在 yx = 2。
13. 15看第 5 位:s1 这位是 "x",s2 这位是 "x"。两个字符一样。
14. 16这位 s1 和 s2 都是 "x",本来就一样,不用动它,标成蓝色跳过,计数都不变。
15. 17看第 6 位:s1 这位是 "x",s2 这位是 "y"。两个字符不一样,得分个类。
16. 18这位 s1 是 "x"、s2 是 "y",属于 xy 类,标成绿色,xy 计数加一,现在 xy = 3。
17. 19看第 7 位:s1 这位是 "y",s2 这位是 "x"。两个字符不一样,得分个类。
18. 20这位 s1 是 "y"、s2 是 "x",属于 yx 类,标成红色,yx 计数加一,现在 yx = 3。
19. 218 个位置全看完:绿色 xy 类有 3 个(第 0、3、6 位),红色 yx 类有 3 个(第 2、4、7 位),蓝色相同位跳过 2 个。不匹配合计 6 个,是偶数,说明能配平、有解。下面开始配对算次数。
20. 22先看绿色 xy 类。第 0 位和第 3 位都是「s1 是 x、s2 是 y」。把 s1 第 0 位的 "x" 和 s2 第 3 位的 "y" 对调一次,这两位就同时对齐了。两个同类不匹配,一次交换全消掉,已用 1 次。
21. 23xy 类一共 3 个,两两配走一对,还剩第 6 位这一个 xy 落单,先放着,等会儿和落单的 yx 一起处理。
22. 24再看红色 yx 类。第 2 位和第 4 位都是「s1 是 y、s2 是 x」,同样一次交换就能把这两位一起摆平,累计已用 2 次。
23. 25yx 类也是 3 个,配走一对后剩第 7 位这一个 yx 落单。现在台面上剩一个 xy(第 6 位)和一个 yx(第 7 位)。
24. 26落单这一个 xy 和一个 yx 不同类,不能一次解决。得先花一次交换把其中一个变成和另一个同类(比如把它俩先弄成两个 yx),再花一次消掉,这一对总共 2 次。加上前面两次,累计 4 次。
25. 27汇总:xy 类 3 个出 1 对、yx 类 3 个出 1 对,各 1 次;最后落单的 xy 加 yx 那一对 2 次。合起来 1 加 1 加 2 等于 4 次,跟开头说的答案对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.size(); ++i) {
            char a = s1[i], b = s2[i];
            xy += a < b;
            yx += a > b;
        }
        if ((xy + yx) % 2) {
            return -1;
        }
        return xy / 2 + yx / 2 + xy % 2 + yx % 2;
    }
};

import java.util.*;
class Solution {
    public int minimumSwap(String s1, String s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.length(); ++i) {
            char a = s1.charAt(i), b = s2.charAt(i);
            if (a < b) {
                ++xy;
            }
            if (a > b) {
                ++yx;
            }
        }
        if ((xy + yx) % 2 == 1) {
            return -1;
        }
        return xy / 2 + yx / 2 + xy % 2 + yx % 2;
    }
}

复杂度

面试官可能追问