用 C++ 编写程序，查找 K 相似字符串的 K 值

pythonserver side programmingprogramming更新于 2025/12/9 13:00:17

假设我们有两个字符串 s 和 t。如果我们可以将 s 中两个字母的位置交换 K 次，得到的字符串为 t，则这两个字符串是 K 相似的。我们有两个字谜 s 和 t，我们必须找到使 s 和 t 相似度为 K 的最小 K。

因此，如果输入为 s = "abc", t = "bac"，则输出为 1。

要解决这个问题，我们将遵循以下步骤 −

定义一个函数 swapp()，它将接受字符串 s、i、j，
x := s[i], y := s[j]
s[i] := y, s[j] := x
从主方法执行以下操作 −
如果 A 与 B 相同，则:，返回0
定义一个集合visited
将A插入visited中
定义一个队列q，将A插入q中
初始化lvl := 1，当q不为空时，更新(将lvl增加1)，执行−
- sz := q的大小
- 当sz非零时，在每次迭代中将sz减少1，执行:
  - curr := q的第一个元素
  - 从q中删除元素
  - i := 0
  - while (i < curr 的大小，且 curr[i] 与 B[i] 相同)，则执行
    - (将 i 增加 1)
  - 初始化 j := i + 1，当 j < curr 的大小时，更新(将 j 增加 1)，则执行
    - 如果 curr[i] 与 curr[j] 相同，则:
      - 忽略以下部分，跳至下一次迭代
    - 如果 curr[j] 不等于 B[i]，则:
      - 忽略以下部分，跳至下一次迭代
    - 如果 curr[j] 与 B[j] 相同，则:
      - 忽略以下部分，跳至下一次迭代
    - swapp(curr, i, j)
    - 如果 curr 与 B 相同，则:
      - 返回 lvl
    - 如果没有调用 count(curr) of accessed，则:
      - 将 curr 插入到 accessed 中
      - 将 curr 插入到 q 中
    - swapp(curr, i, j)
返回 -1

示例

让我们看看下面的实现以便更好地理解

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
   int kSimilarity(string A, string B) {
      if (A == B)
         return 0;
      unordered_set<string> visited;
      visited.insert(A);
      queue<string> q;
      q.push(A);
      for (int lvl = 1; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            string curr = q.front();
            q.pop();
            int i = 0;
            while (i < curr.size() && curr[i] == B[i])
               i++;
            for (int j = i + 1; j < curr.size(); j++) {
               if (curr[i] == curr[j])
                  continue;
               if (curr[j] != B[i])
                  continue;
               if (curr[j] == B[j])
                  continue;
               swapp(curr, i, j);
               if (curr == B)
                  return lvl;
               if (!visited.count(curr)) {
                  visited.insert(curr);
                  q.push(curr);
               }
               swapp(curr, i, j);
            }
         }
      }
      return -1;
   }
   void swapp(string &s, int i, int j) {
      char x = s[i];
      char y = s[j];
      s[i] = y;
      s[j] = x;
   }
};

main(){
   Solution ob;
   cout << (ob.kSimilarity("abc", "bac"));
}