| title | date | tags | |
|---|---|---|---|
用BFS解决交换问题---LeetCode854(BFS) |
2022-09-21 13:11:11 -0700 |
|
日期: 2022-09-21
对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
示例 1：
输入：s1 = "ab", s2 = "ba" 输出：1 示例 2：
输入：s1 = "abc", s2 = "bca" 输出：2
好久没有做过这么难的题了。。。是我太菜。
这道题就是直接用bfs来做暴力搜索，然后使用一个unordered_set来记录已经处理过的序列，如果处理过了就直接剪枝，看起来很简单但是其实写起来还挺麻烦的。。。而且对于一道bfs的题来说，这道题有一些非主流。
首先完整的代码在这里：
class Solution {
public:
vector<string> next(string& s1, string& s2){
vector<string> nexts;
int len = s1.size();
int i = 0;
for(i=0;i<len;i++){
if(s1[i] != s2[i]){
break;
}
}
for(int j=i+1;j<len;j++){
if(s1[i] == s2[j]){
swap(s1[i],s1[j]);
nexts.push_back(s1);
swap(s1[i],s1[j]);
}
}
return nexts;
}
int kSimilarity(string s1, string s2) {
queue<string> q;
unordered_set<string> vis;
q.push(s1);
vis.insert(s1);
int ans = 0;
while(1){
int len = q.size();
for(int i =0; i<len;i++){
string curString = q.front();
q.pop();
if(curString == s2){
return ans;
}
for(auto& x:next(curString,s2)){
if(!vis.count(x)){ //还没找过
vis.insert(x);
q.push(x);
}
}
}
ans += 1;
}
}
};这里使用了一个next函数来判断，对于一个前面有一定长度已经匹配好的字符串s1，它后续允许进行哪些变换来使得它能够更为接近s2。
上面的这种写法是没有问题的，但是之前我写的是另外一种写法，这种写法会直接tle，也比较傻逼。
vector<string> next(string& s1, string& s2){
vector<string> nexts;
int len = s1.size();
for(int i=0;i<len;i++){
if(s1[i] == s2[i]){
continue;
}
for(int j=i+1;j<len;j++){
if(s1[i] == s2[j]){
swap(s1[i],s1[j]);
nexts.push_back(s1);
swap(s1[i],s1[j]);
}
}
}
return nexts;
}这种写法是直接套了两层循环(🙅♂️)，这相当于是把i这个位置后的字符串也拿进来处理了，但是这是不对的，因为你首先得保证i这个位置匹配好了。
这个完全是我的问题了，当然也是因为这道题的BFS比较非主流。
一般来说，BFS都是
while(!q.empty()){
// some code
}但是这道题不行，因为我没有带着ans去dfs。如果用一个结构体去存ans的话，其实也可以写成上面的那种写法。
不过这里我就是直接ans++了，因此写法就变成了:
while(1){
for(xxxxx){
xxx
}
}这里正确的写法是:
int len = q.size();
for(int i =0; i<len;i++){但是如果直接写成了
for(int i =0; i<q.size();i++){就寄了，因为q的size一直在变。一般很少碰到这个问题所以也没引起我的注意，仔细一想这么写就是有问题的，因为每次判断时都会去读取q.size()，当然如果你写成
for(int i =q.size(); i>0;i--){就没问题了，因为初始化这里只有一次。
感觉这种坑写在这里有点侮辱智商，不过。。。至少也是坑过我的。。。是我太菜。
854. 相似度为 K 的字符串 - 力扣（LeetCode）
[Python3/Java/C++/Go] 一题双解：朴素 BFS + 启发式 A* 搜索 - 相似度为 K 的字符串 - 力扣（LeetCode）