LeetCode 854. 相似度为 K 的字符串

题目描述
字符串 s1 和 s2 是字母异位词（即包含相同字符但排列不同）。每次操作允许交换 s1 中任意两个字符的位置。目标是使 s1 等于 s2。需要找到最少交换次数，使得 s1 与 s2 完全相同。这个最少交换次数被定义为两个字符串的“相似度”。如果无法通过交换使 s1 变为 s2，则返回 -1，但题目保证 s1 和 s2 是字母异位词，因此总有解。

示例
输入：s1 = "abc", s2 = "bca"
输出：2
解释：

• 第一次交换 s1[0] 和 s1[1]，得到 "bac"
• 第二次交换 s1[1] 和 s1[2]，得到 "bca" = s2

解题思路

这是一个搜索最短路径问题，可以抽象为：

• 状态：当前的 s1 字符串。
• 初始状态：给定的 s1。
• 目标状态：s1 == s2。
• 状态转移：交换 s1 中的任意两个字符，生成新状态。
• 代价：每次交换计数为 1，求最少交换次数。

关键难点
直接 BFS 状态过多：字符串长度最多为 20，字符为小写字母。最坏情况状态数可达 20!，必须优化。

优化思路

1. 贪心匹配位置：对于当前位置 i，如果 s1[i] == s2[i]，则不需要交换。
2. 剪枝策略：每次只交换那些能使至少一个位置匹配正确的字符。
3. 启发式搜索（A*）：使用当前状态与目标状态不同字符位置的个数除以 2（因为一次交换最多修复两个不匹配位置）作为启发函数的下界估计，加快搜索。

但本题更实用的方法是：有限深度的 BFS + 回溯（DFS），因为相似度 K 通常不会太大。官方题解常用BFS 或 IDA*。

详细解题步骤

步骤1：问题分析

设字符串长度为 n。
定义不匹配位置：s1[i] != s2[i] 的位置 i。
每次交换操作可以改变两个位置 i 和 j 的字符：

• 如果交换后 s1[i] == s2[i] 且 s1[j] == s2[j]，则一次交换修复两个不匹配（最优）。
• 如果只修复一个，另一个可能仍不匹配或变成匹配。
• 目标是最小化交换次数，相当于用最少的交换修复所有不匹配。

步骤2：BFS 搜索框架

从初始 s1 开始，BFS 层数即为交换次数。
在每一状态，枚举所有交换对 (i, j)，其中 i < j，生成新字符串 next_s1，若未访问过则加入队列。
当 next_s1 == s2 时，返回当前层数。

简单 BFS 代码框架（会超时，但有助于理解）：

def kSimilarity(s1, s2):
    if s1 == s2:
        return 0
    n = len(s1)
    queue = deque([s1])
    visited = {s1}
    steps = 0
    while queue:
        for _ in range(len(queue)):
            cur = queue.popleft()
            # 找到第一个 cur[i] != s2[i] 的位置 i
            i = 0
            while i < n and cur[i] == s2[i]:
                i += 1
            # 从 i+1 开始找 j，使得交换 cur[i] 和 cur[j] 后 cur[j] == s2[i]
            for j in range(i + 1, n):
                if cur[j] == s2[i]:
                    nxt = list(cur)
                    nxt[i], nxt[j] = nxt[j], nxt[i]
                    nxt_str = ''.join(nxt)
                    if nxt_str == s2:
                        return steps + 1
                    if nxt_str not in visited:
                        visited.add(nxt_str)
                        queue.append(nxt_str)
        steps += 1
    return -1

优化点：只交换能使 cur[i] 变成 s2[i] 的 j，因为交换无关字符不会改善匹配数。

步骤3：进一步优化——每次至少修复一个匹配

在上述 BFS 中，我们在位置 i（第一个不匹配处）寻找 j 使得 cur[j] == s2[i]。交换后，cur[i] 必然匹配正确。这样保证每次交换至少修复一个位置，减少状态扩展。

为什么选第一个不匹配位置？
这样可以减少重复状态，且不丢失最优解。因为不按顺序修复可能增加交换次数。

步骤4：处理多次重复字符

当字符串有重复字符时，可能有多个 j 满足 cur[j] == s2[i]。BFS 需要尝试所有可能的 j，因为不同的选择会影响后续匹配。

例如：s1="abac", s2="baca"
第一步：i=0, s1[0]='a', s2[0]='b'，寻找 j 使得 s1[j]='b'，发现 j=1。交换得 "baac"。
但可能另一种交换更好？需要 BFS 尝试。

步骤5：BFS 实现细节

1. 使用队列进行层次遍历。
2. 使用集合记录已访问状态，避免重复搜索。
3. 每层 steps 增加 1。
4. 当弹出状态与 s2 相等时，返回 steps。

最终代码（优化 BFS）：

from collections import deque

def kSimilarity(s1: str, s2: str) -> int:
    if s1 == s2:
        return 0
    n = len(s1)
    queue = deque([s1])
    visited = {s1}
    steps = 0
    while queue:
        for _ in range(len(queue)):
            cur = queue.popleft()
            # 找第一个不匹配的位置 i
            i = 0
            while cur[i] == s2[i]:
                i += 1
            # 找所有可能的 j 进行交换
            for j in range(i + 1, n):
                if cur[j] == s2[i] and cur[j] != s2[j]:  # 如果 cur[j] 已经匹配 s2[j] 就不交换它
                    nxt = list(cur)
                    nxt[i], nxt[j] = nxt[j], nxt[i]
                    nxt_str = ''.join(nxt)
                    if nxt_str == s2:
                        return steps + 1
                    if nxt_str not in visited:
                        visited.add(nxt_str)
                        queue.append(nxt_str)
        steps += 1
    return -1  # 实际不会到这里，因为总有解

步骤6：复杂度分析

• 最坏情况：每个状态扩展 O(n²) 个新状态，但剪枝后远小于。
• 状态数受限于不匹配位置数，实际运行可通过。

测试示例
s1="abc", s2="bca"

• 初始: "abc"
• 步骤0: i=0, 找 j=1 (因为 s1[1]='b'=s2[0])，交换得 "bac"，加入队列。
• 步骤1: 从 "bac" 出发，i=1, s1[1]='a', s2[1]='c'，找 j=2 (s1[2]='c')，交换得 "bca"，匹配成功，返回步骤1+1=2。

总结

本题是最小交换次数使字符串相等问题，本质是状态空间搜索。通过 BFS + 剪枝（每次修复第一个不匹配位置，且只交换能匹配目标字符的位置）可以在合理时间内求解。核心在于避免无效交换，减少状态爆炸。对于长度≤20 的字符串，该 BFS 方法可行。