ABC221B typo

题意分析

给定两个字符串 $s$ 和 $t$，你可以对字符串 $s$ 执行如下操作：

• 交换相邻的两个字符一次，或者
• 什么都不做。

问：是否可以通过不超过一次操作使得 $s$ 转变为 $t$。

---

解题思路

本题的目标是判断字符串 $s$ 是否可以通过一次相邻字符交换操作变成字符串 $t$。

分析操作

我们可以考虑如下两种情况：

• 不进行操作：

  • 如果原字符串 $s$ 与目标字符串 $t$ 完全一致，则直接输出 Yes。

• 进行一次相邻字符交换：

  • 枚举 $s$ 中所有的相邻字符对；
  • 尝试对每一对进行一次交换，形成一个新的字符串；
  • 检查该新字符串是否与 $t$ 一致；
  • 如果存在一次交换后的字符串与 $t$ 相等，则输出 Yes。

如果上述两种情况都不满足，则输出 No。

---

交换函数

C++ 中有一个交换函数名为 swap()，用于交换两个变量的值。 - 该函数无返回值，直接交换修改。 - 例如本题交换相邻两个字符，即 swap(s[i], s[i + 1])。

• 需要注意交换以后，字符串的形态就变了，因此本题先创建一个临时变量字符串 string temp = s，然后每次在 temp 上操作，操作后和 $t$ 比较是否相等即可。

示例讲解

以样例 $1$ 为例：

• $s = \texttt{abc}$，$t = \texttt{acb}$
• 尝试将 $s$ 的第 $1$ 和 $2$ 位交换得到 $bac\not= t$
• 尝试将第 $2$ 和 $3$ 位交换得到 $acb=t$
• 存在一种合法操作，因此输出 Yes

再看样例 $2$：

• $s = \texttt{aabb}$，$t = \texttt{bbaa}$
• 无论交换哪一对相邻字符，都无法得到目标字符串，因此输出 No

---

时间复杂度分析

• 枚举所有 $s$ 中的相邻字符对最多 $O(N)$ 次；
• 每次模拟交换后比较字符串是否等于 $t$，耗时 $O(N)$；
• 总体复杂度为 $O(N^2)$，但由于 $N \leq 100$，可以接受。

---

总结

• 本题考查字符串比较与相邻字符交换操作；
• 注意考虑无需交换即可达成的情况；
• 利用暴力枚举方式尝试每一对相邻字符交换即可；
• 属于典型的模拟题，适合字符串基础训练。