在C++中寻找K-Similar字符串的K值的程序

假设我们有两个字符串s和t。当我们可以精确交换s中的两个字母位置K次，使结果字符串为t时，这两个字符串为K-similar。我们有两个变位词s和t，我们必须找到使s和t成为K-similar的最小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
  - 当（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
  - 如果未调用visited的count（curr），则：
    - 将curr插入visited中
    - 将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"));
}