Find and Replace

题意

给定两个等长字符串 s 和 t，字符只包含大小写英文字母。

一次操作可以选择两个字符 c1 和 c2，把当前字符串中所有 c1 同时替换成 c2。

对每组数据，求把 s 变成 t 的最少操作数；如果不可能，输出 -1。

思路

先看一个小数据暴力。它直接把整个字符串当作状态，用 BFS 枚举每一次“全局字符替换”。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:05
 * update_at: 2026-07-11 19:08
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const string ALL = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

int T;

int bfs(string s, string target) {
    if (s == target) return 0;

    bool used[256];
    memset(used, 0, sizeof(used));

    vector<char> letters;
    for (int i = 0; i < (int)s.size(); i++) {
        if (!used[(unsigned char)s[i]]) {
            used[(unsigned char)s[i]] = true;
            letters.push_back(s[i]);
        }
        if (!used[(unsigned char)target[i]]) {
            used[(unsigned char)target[i]] = true;
            letters.push_back(target[i]);
        }
    }

    // 小数据暴力额外加入一个临时字符，用来打破环。
    for (int i = 0; i < (int)ALL.size(); i++) {
        if (!used[(unsigned char)ALL[i]]) {
            letters.push_back(ALL[i]);
            break;
        }
    }

    queue<string> q;
    map<string, int> dist;
    q.push(s);
    dist[s] = 0;

    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        int d = dist[cur];

        for (int i = 0; i < (int)letters.size(); i++) {
            char from = letters[i];
            bool has_from = false;
            for (int p = 0; p < (int)cur.size(); p++) {
                if (cur[p] == from) {
                    has_from = true;
                    break;
                }
            }
            if (!has_from) continue;

            for (int j = 0; j < (int)letters.size(); j++) {
                char to = letters[j];
                if (from == to) continue;

                string nxt = cur;
                for (int p = 0; p < (int)nxt.size(); p++) {
                    if (nxt[p] == from) {
                        nxt[p] = to;
                    }
                }

                if (dist.find(nxt) == dist.end()) {
                    dist[nxt] = d + 1;
                    if (nxt == target) {
                        return d + 1;
                    }
                    q.push(nxt);
                }
            }
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        string s, t;
        cin >> s >> t;
        cout << bfs(s, t) << '\n';
    }

    return 0;
}

满分做法把每个字符看成图上的点。若某个位置满足 s[i] = x、t[i] = y，就说明最终所有 x 都必须变成 y，也就是一条有向边：

text

1x -> y

如果同一个字符 x 同时要求变成两个不同字符，显然无解。

还有一个特殊无解情况：如果 $s != t$ ，并且目标串 t 已经包含了全部 52 种大小写字母，那么没有任何空闲字符可以当临时字符，无法完成非平凡替换。

如果没有无解，先统计所有非自环边。每条 x -> y 且 $x != y$ 的边至少需要一次操作，所以这些边贡献基础答案。

麻烦在于环。例如样例最后一组 ABCD -> BACD 中有：

flowchart LR
  A["A"] --> B["B"]
  B --> A

这张图展示的是 A 和 B 互相替换形成的纯环。如果直接执行 A -> B，原来的 B 会和新来的 B 混在一起，之后无法区分。所以必须借一个临时字符，类似 A -> E -> B，因此这个环比边数多花一次操作。

但不是所有环都要额外加一。如果环上某个点还有来自环外的入边，环外字符可以充当打破环的入口，官方解析称这种情况不需要额外次数。

所以答案是：

text

1非自环边数 + 没有额外入边的有向环个数

实现时，to[x] 表示字符 x 最终要变成谁。由于每个点出度最多为 1，这是一个函数图。用 seen[] 沿着 to[] 走，就能找出环；再用 indeg[] 判断环上是否存在入度大于 1 的点。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:05
 * update_at: 2026-07-11 19:08
 */
#include <bits/stdc++.h>
using namespace std;

const int SIGMA = 52;

int T;

int char_id(char c) {
    if ('a' <= c && c <= 'z') {
        return c - 'a';
    }
    return 26 + (c - 'A');
}

void solve_one() {
    string s, t;
    cin >> s >> t;

    int to[SIGMA];
    int indeg[SIGMA];
    int seen[SIGMA];
    bool in_target[SIGMA];
    memset(indeg, 0, sizeof(indeg));
    memset(seen, 0, sizeof(seen));
    memset(in_target, 0, sizeof(in_target));

    for (int i = 0; i < SIGMA; i++) {
        to[i] = -1;
    }

    bool possible = true;
    for (int i = 0; i < (int)s.size(); i++) {
        int x = char_id(s[i]);
        int y = char_id(t[i]);
        in_target[y] = true;

        if (to[x] != -1 && to[x] != y) {
            possible = false;
        }
        to[x] = y;
    }

    int target_cnt = 0;
    for (int i = 0; i < SIGMA; i++) {
        if (in_target[i]) target_cnt++;
    }

    if (s != t && target_cnt == SIGMA) {
        possible = false;
    }

    if (!possible) {
        cout << -1 << '\n';
        return;
    }

    int ans = 0;
    for (int i = 0; i < SIGMA; i++) {
        if (to[i] != -1 && to[i] != i) {
            ans++;
            indeg[to[i]]++;
        }
    }

    // 函数图中，纯环需要额外借一个临时字符打破。
    for (int start = 0; start < SIGMA; start++) {
        if (seen[start] != 0) continue;

        int x = start;
        while (x != -1 && seen[x] == 0) {
            seen[x] = start + 1;
            x = to[x];
        }

        if (x != -1 && to[x] != x && seen[x] == start + 1) {
            int y = x;
            bool has_extra_in = false;
            do {
                if (indeg[y] > 1) {
                    has_extra_in = true;
                }
                y = to[y];
            } while (y != x);

            if (!has_extra_in) {
                ans++;
            }
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

复杂度

字符集大小固定为 52。

每组数据只需要扫描字符串并在 52 个点上找环。若字符串长度为 $L$ ，时间复杂度为 $O(L+52)$ ，空间复杂度为 $O(52)$ 。

总结

本题的关键是把“全局替换字符”理解成字符之间的映射关系。

出度冲突对应无解；非自环边对应必要操作；纯环因为需要临时字符打破，所以额外加一次。

目录

题意

思路

代码

复杂度

总结