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