小欧的字符交换
小欧的字符交换
OPPO 笔试真题 · 2023 秋招 · 后端岗
判题请到牛客原题提交。
题目描述
小欧拿到了两个长度相等的字符串和。她想知道能否交换中两个相邻的字符,使得和相等?请注意,最多只有1次交换的机会!
一共有组询问。
输入格式
第一行输入一个正整数,代表询问次数。
每组输入两行仅包含小写字母字符串,分别代表字符串和字符串。
和的长度不超过100。
输出格式
对于每组询问,输出一行答案。若可以交换两个相邻字符使得和相等,则输出"Yes"。否则输出"No"。
示例
示例 1
输入:
3
acb
cab
abcxz
cbaxz
wa
wa输出:
Yes
No
Yes说明:
第一组询问,交换前两个字符即可。
第二组询问,无法进行一次“交换相邻两个字符”使得两字符串相等。
第三组询问,字符串本身相等,不需要交换。
解题思路
第一步:理解问题本质
一次「交换相邻两个字符」只会改变两个位置上的字符,其他位置原封不动。
所以可以先比较 s 和 t,找出所有不同的位置:
- 0 处不同:
s已经等于t,题目允许「最多一次」,交换 0 次即可; - 1 处不同:交换必然改动两个位置,修好这一位的同时会弄坏另一位,不可能成功;
- 2 处不同:只有交换这两个位置才可能修好,于是要求它们相邻且交叉相等;
- 3 处及以上:一次交换最多消掉两处差异,不可能成功。
第二步:2 处不同时的两个条件
设不同的两个位置是 i 和 j(i < j)。
- 必须相邻:交换只能发生在相邻位置,所以要有
j == i + 1。 - 必须交叉相等:交换后
s[i]会变成原来的s[j],要让它等于t[i];
同理s[j]会变成原来的s[i],要让它等于t[j]。也就是s[i] == t[j]且s[j] == t[i]。
两个条件同时满足才输出 Yes。
第三步:每组询问独立处理
q 组询问之间没有关系,逐组判断即可。读入时用 split() 一次性拿到所有 token,
按「两个一组」的顺序取 s 和 t。
完整代码实现
import sys
def can_make_equal(s: str, t: str) -> bool:
"""最多交换一对相邻字符,s 能否变成 t"""
if s == t:
return True
diff = [i for i in range(len(s)) if s[i] != t[i]]
if len(diff) != 2:
return False
i, j = diff
# 必须相邻,且两个字符互换后正好各自对上
return j == i + 1 and s[i] == t[j] and s[j] == t[i]
def solve() -> None:
"""逐组询问判断并输出 Yes / No"""
data = sys.stdin.read().split()
if not data:
return
q = int(data[0])
out = []
pos = 1
for _ in range(q):
s, t = data[pos], data[pos + 1]
pos += 2
out.append("Yes" if can_make_equal(s, t) else "No")
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()示例推演
输入共 3 组询问。
第 1 组:s = "acb",t = "cab"。
| 位置 | 0 | 1 | 2 |
|---|---|---|---|
| s | a | c | b |
| t | c | a | b |
| 是否相同 | 否 | 否 | 是 |
两处不同,位置 0 和 1 相邻;交叉检查 s[0] = 'a' = t[1]、s[1] = 'c' = t[0],都成立。
交换前两位得到 "cab",与 t 相同,输出 Yes。
第 2 组:s = "abcxz",t = "cbaxz"。
| 位置 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| s | a | b | c | x | z |
| t | c | b | a | x | z |
| 是否相同 | 否 | 是 | 否 | 是 | 是 |
两处不同,但位置 0 和 2 不相邻,无论交换哪一对相邻字符都改不到这两个位置,
输出 No。
第 3 组:s = "wa",t = "wa",两串相同,交换 0 次即可,输出 Yes。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 统计不同位置 | O(q · L) | O(L) | L 为字符串长度,推荐 |
| 枚举所有相邻交换再比较 | O(q · L²) | O(L) | 同样正确,但没必要 |
易错点总结
1. 忘了「零次交换」也合法
题目说的是「最多只有 1 次交换的机会」。s 本来就等于 t 时要输出 Yes,
不能因为「没执行交换」就判成 No。
2. 只检查不同位置的数量,忘了相邻
两处不同但隔着很远时,一次相邻交换根本碰不到它们。
必须先判断 j == i + 1。
3. 只检查相邻,忘了交叉相等
"ab" 与 "ac" 只有一处不同,直接判 No 是对的;
但 "ab" 与 "cb" 也是一处不同,同样要判 No —— 交换会把原本正确的那一位改坏。
4. 试图把字符「换成」目标字符
本次操作只有「交换」这一种,不能把某个字符直接改成别的字符。
两者的区别在于:交换只是调换位置,字符的多重集合不变。
扩展思考
- 如果允许任意两个位置交换(不要求相邻),条件就退化成
「两处不同且交叉相等」,去掉相邻判断即可。 - 如果允许最多
k次相邻交换,问题会变成计算把s变成t所需的
逆序对距离,用双指针或置换环来算。 - 如果允许交换
s内部的任意两个字符且s、t长度不等,还要先比较字符频次是否一致。