C ++中的K相似字符串

假设我们有两个字符串A和B。如果我们可以将A中的两个字母的位置恰好交换K次，使得结果字符串为B，那么这两个字符串是K相似的（其中K是一个非负整数）。在两个字谜A和B之间，我们必须找到与A和B类似的最小K。

因此，如果输入类似于A =“ abc”，B =“ bac”，则输出将为2。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数swapp()，它将采用字符串s，i，j，

• x：= s [i]，y：= s [j]

• s [i]：= y，s [j]：= x

• 从主要方法中执行以下操作-

• 如果A与B相同，则：，返回0

• 定义一组参观

• 将A插入已访问

• 定义一个队列q，将A插入q

• 对于初始化lvl：= 1，当非q为空时，更新（将lvl增加1），执行-

• curr：= q的第一个元素

• 从q删除元素

• i：= 0

• 而（i <curr和curr [i]的大小与B [i]相同），则执行-

• 对于初始化j：= i + 1，当j <当前大小时，更新（将j增加1），-

• （将i增加1）

• 将curr插入访问

• 将curr插入q

• 返回lvl

• 忽略以下部分，跳至下一个迭代

• 忽略以下部分，跳至下一个迭代

• 忽略以下部分，跳至下一个迭代

• 如果curr [i]与curr [j]相同，则-

• 如果curr [j]不等于B [i]，则-

• 如果curr [j]与B [j]相同，则-

• swapp(curr,i,j)

• 如果curr与B相同，则-

• 如果没有拜访的呼叫计数(curr)，则-

• swapp(curr,i,j)

• sz：= q的大小

• 当sz为非零值时，请在每次迭代中将sz减1，然后执行-

• 返回-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"));
}

输入值

"abc", "bac"

输出结果

1