在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)
- curr:= q的第一个元素
-
返回-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