LeetCode 854. 相似度为 K 的字符串
字数 3883 2025-12-19 22:09:48

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

题目描述：
给定两个字符串 s1 和 s2，它们长度相同，且只包含字母 'a' 到 'f' 六个小写字母。一次操作可以交换 s1 中任意两个字符的位置。请问至少需要多少次操作，可以将 s1 变成 s2？换句话说，求 s1 和 s2 的“相似度”（即最小交换次数）。

例如：

  • 输入：s1 = "aabc", s2 = "abca"
  • 输出：2
  • 解释：一种方案是交换 s1[1] 和 s1[2] 得到 "abac"，然后交换 s1[2] 和 s1[3] 得到 "abca"。

题目本质是求通过交换字符使两个字符串相等的最少交换次数，字符串长度不超过 20。

解题过程循序渐进讲解

步骤 1：问题理解与转化

题目中说一次操作是交换 s1 中的两个字符，最终要让 s1 变得和 s2 一样。
我们可以把问题看作是对 s1 的字符进行重新排列，使得它等于 s2。
每次交换可以纠正两个位置上的字符错配。

关键观察：

  • 如果 s1[i] 已经等于 s2[i]，这个位置不需要动。
  • 如果 s1[i] != s2[i]，那么 s1[i] 最终必须被放到某个 j 满足 s2[j] == s1[i] 的位置上。
  • 这其实是一个图匹配问题：把错配的位置看成节点，如果位置 i 的字符应该是 s2[i]，但它现在是 s1[i]，那么它需要找到另一个位置 j 的字符 s1[j] 是 s2[i]，然后交换。

另一种思路：
设 s1 和 s2 在位置 i 不同，那么 s1[i] 需要被放到 s2 中对应这个字符的某个位置。
如果我们只考虑不同的位置，可以构造一个有向图：节点是位置，从位置 i 到位置 j 有一条边表示 s1[i] == s2[j]。
这样每个节点的出度为 1（因为 s1[i] 必须去某个 j 满足 s2[j] == s1[i]），入度也是 1，因此图是若干环的集合。
每个环的长度为 L，则让这个环内字符归位需要 L-1 次交换。
但这是理想情况吗？这里要注意：我们只能交换 s1 的字符，并且一次交换涉及两个位置，如果环与环之间交换可以节省次数吗？

更直接的方法：已知最少交换次数的经典公式：
如果把错配位置之间的对应关系用图表示成若干环，每个环需要 环长度-1 次交换，总最少交换次数 = 总错配位置数 - 环的个数。
但这是对于“每个位置上的数都要放到对应位置”的排列最小交换次数（比如数组排序）。
在这个问题中，字符可能重复，所以不能直接用这个公式，因为一个字符可能可以去多个目标位置，我们需要选择最优的匹配方式，使得最后形成的环数最多（因为交换次数 = 不同位置数 - 环数）。

举个例子：
s1 = "aabc", s2 = "abca"
不同位置是 0,1,2,3 吗？比较：
s1[0]=a, s2[0]=a → 相同，所以位置0相同，不需要动。
s1[1]=a, s2[1]=b → 不同
s1[2]=b, s2[2]=c → 不同
s1[3]=c, s2[3]=a → 不同
所以不同位置是 {1,2,3}。

我们为这些不同位置建立映射：
位置1的字符是'a'，它应该变成'b'，但当前位置1的'a'要去哪里？看s2中需要'a'的位置：s2[3]需要'a'（因为s2[3]=a，而s1[3]是'c'），所以可以把位置1的'a'换到位置3，这样位置3就对了，但位置1得到'c'。
这样推导就是搜索过程，因为字符重复，可能的配对方式很多。

因此这个问题不能用简单公式，需要用搜索算法。

步骤 2：搜索状态定义

我们可以用 BFS 搜索状态：
状态是当前的字符串 cur，初始状态是 s1，目标状态是 s2。
每一步交换 cur 的两个位置 i 和 j，得到新状态。
BFS 可以找到最少交换次数。

但字符串长度最大 20，字符只有 6 种，状态数最多 6^20 巨大，不能全部展开。
但 BFS 时，我们只搜索从 s1 到 s2 的路径，很多状态不会访问到。
然而，长度 20 时，不同状态仍然可能非常多，需要优化。

步骤 3：优化思路——只考虑不同位置

因为相同的位置交换没有意义，我们每次交换应该至少让一个位置变正确（或者为后续变正确做准备）。
一个常见优化：在 BFS 时，只考虑那些 cur[i] != s2[i] 的位置 i 进行交换，且最好交换后至少有一个位置匹配上。

更进一步的优化：A* 搜索。
定义启发函数 h(cur) 为当前 cur 与 s2 不同字符的位置数量除以 2 上取整，因为一次交换最多修复两个错位。
即 h(cur) = ceil( mismatch_count / 2 )，其中 mismatch_count 是 cur 与 s2 不同位置的数量。
这个启发函数是可容的（admissible），因为一次交换最多让错位数减少 2，所以实际剩余步数不少于 mismatch_count/2 上取整。

步骤 4：BFS/A* 搜索步骤

  1. 队列存储状态 (cur, steps)，steps 是走到当前状态的交换次数。
  2. 每次从队列取出一个状态，如果 cur == s2，返回 steps。
  3. 否则，找到所有 cur[i] != s2[i] 的位置 i，再找一个 j > i 使得 j 也是错位位置，交换 cur[i] 和 cur[j] 得到新字符串 next。
  4. 如果 next 未访问过，加入队列。
  5. 用优先队列实现 A*，优先级为 steps + h(next)。

但注意：交换时，如果 cur[i] 换到位置 j 后，cur[i] 变得等于 s2[i] 吗？不，是位置 i 的新字符是原来的 cur[j]。
我们交换 i 和 j 后，可能让位置 i 正确（如果 cur[j] == s2[i]），也可能让位置 j 正确（如果 cur[i] == s2[j]），也可能两个都正确，也可能只对一个正确，也可能都不正确但对后续有益。
BFS 会探索所有可能。

步骤 5：具体例子走一遍

s1 = "aabc", s2 = "abca"

初始 cur = "aabc", mismatch 位置 {1,2,3}（0位置已匹配）。

BFS 第一步：

  • 考虑交换 (1,2)：cur[1]='a', cur[2]='b'，交换得 "abac"。比较 s2="abca"：
    • 位置0: a=a ✓
    • 位置1: b=b ✓（修复了位置1）
    • 位置2: a!=c ✗
    • 位置3: c!=a ✗
      mismatch 位置 {2,3}。
  • 交换 (1,3)：cur[1]='a', cur[3]='c'，交换得 "acba"。比较：
    • 位置1: c!=b ✗
    • 位置2: b!=c ✗
    • 位置3: a=a ✓（修复了位置3）
      mismatch 位置 {1,2}。
  • 交换 (2,3)：cur[2]='b', cur[3]='c'，交换得 "aacb"。比较：
    • 位置2: c!=c ✓（修复了位置2）
    • 位置3: b!=a ✗
      mismatch 位置 {3}，但注意位置1: a!=b ✗ 还错，所以 mismatch 是 {1,3}。等一下，检查：
      s1="aabc" 交换(2,3) → "a a c b"（索引0=a,1=a,2=c,3=b）与 s2="a b c a" 比较：
      索引0: a=a ✓
      索引1: a!=b ✗
      索引2: c!=c ✓ 吗？s2[2]=c, cur[2]=c → 对，修复了。
      索引3: b!=a ✗
      所以 mismatch {1,3}。

继续 BFS，最终最短路径是 2 步。
从 "aabc" → 交换(1,2) 得 "abac" → 交换(2,3) 得 "abca"，完成。

步骤 6：实现细节优化

  • 用字符串表示状态，长度 ≤ 20，可以用字符串哈希判重。
  • 只交换错位的位置。
  • 使用启发式搜索加速。

步骤 7：最终算法流程

  1. 如果 s1 == s2，返回 0。
  2. 初始化队列（优先队列），加入 (s1, 0, h(s1))。
  3. 初始化 visited 集合记录访问过的字符串。
  4. 当队列不空：
    • 弹出 (cur, steps, _)。
    • 找出所有满足 cur[i] != s2[i] 的索引 i。
    • 对于每一对 (i, j) 其中 i < j 且都是错位索引：
      • 交换 cur[i] 和 cur[j] 得到 next。
      • 如果 next == s2，返回 steps+1。
      • 如果 next 未访问，加入队列，优先级 steps+1+h(next)。
  5. 返回 -1（实际上题目保证有解）。

步骤 8：复杂度分析

  • 状态数可能很多，但因为有启发函数，实际搜索空间较小。
  • 字符串只有 6 种字符，长度 20，最大不同状态数有限，但依然可能很大，不过测试数据可以通过。

这样，我们就通过 BFS/A* 搜索解决了“相似度为 K 的字符串”问题，求得最少交换次数。

LeetCode 854. 相似度为 K 的字符串 题目描述： 给定两个字符串 s1 和 s2 ，它们长度相同，且只包含字母 'a' 到 'f' 六个小写字母。一次操作可以交换 s1 中任意两个字符的位置。请问至少需要多少次操作，可以将 s1 变成 s2 ？换句话说，求 s1 和 s2 的“相似度”（即最小交换次数）。 例如： 输入：s1 = "aabc", s2 = "abca" 输出：2 解释：一种方案是交换 s1[ 1] 和 s1[ 2] 得到 "abac"，然后交换 s1[ 2] 和 s1[ 3 ] 得到 "abca"。 题目本质是求通过交换字符使两个字符串相等的最少交换次数，字符串长度不超过 20。 解题过程循序渐进讲解 步骤 1：问题理解与转化 题目中说一次操作是交换 s1 中的两个字符，最终要让 s1 变得和 s2 一样。 我们可以把问题看作是对 s1 的字符进行重新排列，使得它等于 s2 。 每次交换可以纠正两个位置上的字符错配。 关键观察： 如果 s1[i] 已经等于 s2[i] ，这个位置不需要动。 如果 s1[i] != s2[i] ，那么 s1[i] 最终必须被放到某个 j 满足 s2[j] == s1[i] 的位置上。 这其实是一个 图匹配问题 ：把错配的位置看成节点，如果位置 i 的字符应该是 s2[i] ，但它现在是 s1[i] ，那么它需要找到另一个位置 j 的字符 s1[j] 是 s2[i] ，然后交换。 另一种思路： 设 s1 和 s2 在位置 i 不同，那么 s1[i] 需要被放到 s2 中对应这个字符的某个位置。 如果我们只考虑不同的位置，可以构造一个有向图：节点是位置，从位置 i 到位置 j 有一条边表示 s1[i] == s2[j] 。 这样每个节点的出度为 1（因为 s1[i] 必须去某个 j 满足 s2[j] == s1[i] ），入度也是 1，因此图是若干环的集合。 每个环的长度为 L ，则让这个环内字符归位需要 L-1 次交换。 但这是理想情况吗？这里要注意： 我们只能交换 s1 的字符，并且一次交换涉及两个位置 ，如果环与环之间交换可以节省次数吗？ 更直接的方法：已知最少交换次数的经典公式： 如果把错配位置之间的对应关系用图表示成若干环，每个环需要 环长度-1 次交换，总最少交换次数 = 总错配位置数 - 环的个数。 但这是对于“每个位置上的数都要放到对应位置”的排列最小交换次数（比如数组排序）。 在这个问题中，字符可能重复，所以不能直接用这个公式，因为一个字符可能可以去多个目标位置，我们需要选择最优的匹配方式，使得最后形成的环数最多（因为交换次数 = 不同位置数 - 环数）。 举个例子： s1 = "aabc", s2 = "abca" 不同位置是 0,1,2,3 吗？比较： s1[ 0]=a, s2[ 0 ]=a → 相同，所以位置0相同，不需要动。 s1[ 1]=a, s2[ 1 ]=b → 不同 s1[ 2]=b, s2[ 2 ]=c → 不同 s1[ 3]=c, s2[ 3 ]=a → 不同 所以不同位置是 {1,2,3}。 我们为这些不同位置建立映射： 位置1的字符是'a'，它应该变成'b'，但当前位置1的'a'要去哪里？看s2中需要'a'的位置：s2[ 3]需要'a'（因为s2[ 3]=a，而s1[ 3 ]是'c'），所以可以把位置1的'a'换到位置3，这样位置3就对了，但位置1得到'c'。 这样推导就是搜索过程，因为字符重复，可能的配对方式很多。 因此这个问题不能用简单公式，需要用 搜索算法 。 步骤 2：搜索状态定义 我们可以用 BFS 搜索状态： 状态是当前的字符串 cur ，初始状态是 s1 ，目标状态是 s2 。 每一步交换 cur 的两个位置 i 和 j ，得到新状态。 BFS 可以找到最少交换次数。 但字符串长度最大 20，字符只有 6 种，状态数最多 6^20 巨大，不能全部展开。 但 BFS 时，我们只搜索从 s1 到 s2 的路径，很多状态不会访问到。 然而，长度 20 时，不同状态仍然可能非常多，需要优化。 步骤 3：优化思路——只考虑不同位置 因为相同的位置交换没有意义，我们每次交换应该至少让一个位置变正确（或者为后续变正确做准备）。 一个常见优化：在 BFS 时，只考虑那些 cur[i] != s2[i] 的位置 i 进行交换，且最好交换后至少有一个位置匹配上。 更进一步的优化：A* 搜索。 定义启发函数 h(cur) 为当前 cur 与 s2 不同字符的位置数量除以 2 上取整，因为一次交换最多修复两个错位。 即 h(cur) = ceil( mismatch_count / 2 ) ，其中 mismatch_count 是 cur 与 s2 不同位置的数量。 这个启发函数是可容的（admissible），因为一次交换最多让错位数减少 2，所以实际剩余步数不少于 mismatch_count/2 上取整。 步骤 4：BFS/A* 搜索步骤 队列存储状态 (cur, steps) ， steps 是走到当前状态的交换次数。 每次从队列取出一个状态，如果 cur == s2 ，返回 steps 。 否则，找到所有 cur[i] != s2[i] 的位置 i ，再找一个 j > i 使得 j 也是错位位置，交换 cur[i] 和 cur[j] 得到新字符串 next 。 如果 next 未访问过，加入队列。 用优先队列实现 A* ，优先级为 steps + h(next) 。 但注意：交换时，如果 cur[i] 换到位置 j 后， cur[i] 变得等于 s2[i] 吗？不，是位置 i 的新字符是原来的 cur[j] 。 我们交换 i 和 j 后，可能让位置 i 正确（如果 cur[j] == s2[i] ），也可能让位置 j 正确（如果 cur[i] == s2[j] ），也可能两个都正确，也可能只对一个正确，也可能都不正确但对后续有益。 BFS 会探索所有可能。 步骤 5：具体例子走一遍 s1 = "aabc", s2 = "abca" 初始 cur = "aabc", mismatch 位置 {1,2,3}（0位置已匹配）。 BFS 第一步： 考虑交换 (1,2)：cur[ 1]='a', cur[ 2 ]='b'，交换得 "abac"。比较 s2="abca"： 位置0: a=a ✓ 位置1: b=b ✓（修复了位置1） 位置2: a !=c ✗ 位置3: c !=a ✗ mismatch 位置 {2,3}。 交换 (1,3)：cur[ 1]='a', cur[ 3 ]='c'，交换得 "acba"。比较： 位置1: c !=b ✗ 位置2: b !=c ✗ 位置3: a=a ✓（修复了位置3） mismatch 位置 {1,2}。 交换 (2,3)：cur[ 2]='b', cur[ 3 ]='c'，交换得 "aacb"。比较： 位置2: c !=c ✓（修复了位置2） 位置3: b !=a ✗ mismatch 位置 {3}，但注意位置1: a !=b ✗ 还错，所以 mismatch 是 {1,3}。等一下，检查： s1="aabc" 交换(2,3) → "a a c b"（索引0=a,1=a,2=c,3=b）与 s2="a b c a" 比较： 索引0: a=a ✓ 索引1: a !=b ✗ 索引2: c!=c ✓ 吗？s2[ 2]=c, cur[ 2 ]=c → 对，修复了。 索引3: b !=a ✗ 所以 mismatch {1,3}。 继续 BFS，最终最短路径是 2 步。 从 "aabc" → 交换(1,2) 得 "abac" → 交换(2,3) 得 "abca"，完成。 步骤 6：实现细节优化 用字符串表示状态，长度 ≤ 20，可以用字符串哈希判重。 只交换错位的位置。 使用启发式搜索加速。 步骤 7：最终算法流程 如果 s1 == s2，返回 0。 初始化队列（优先队列），加入 (s1, 0, h(s1)) 。 初始化 visited 集合记录访问过的字符串。 当队列不空： 弹出 (cur, steps, _) 。 找出所有满足 cur[i] != s2[i] 的索引 i。 对于每一对 (i, j) 其中 i < j 且都是错位索引： 交换 cur[ i] 和 cur[ j ] 得到 next。 如果 next == s2，返回 steps+1。 如果 next 未访问，加入队列，优先级 steps+1+h(next)。 返回 -1（实际上题目保证有解）。 步骤 8：复杂度分析 状态数可能很多，但因为有启发函数，实际搜索空间较小。 字符串只有 6 种字符，长度 20，最大不同状态数有限，但依然可能很大，不过测试数据可以通过。 这样，我们就通过 BFS/A* 搜索解决了“相似度为 K 的字符串”问题，求得最少交换次数。