优选算法_最小基因变化_bfs_C++

一.题目解析算法讲解:1.改变一个字符之后,需要在bank里面看一下存不存在,所以我们可以将bank数组导入到一个hash表里面快速判断存不存在.2.遍历全部情况:一个指针遍历start的8个字母,再创建一个string changeAGCT指针遍历一个位置四种情况.3.枚举出来的字符串只有bank里面的才需要加入队列4.使用hash表来表示该字符串已经遍历5.BFS基础:队列 queuestringq实现宽搜判断该位置是否遍历(这里使用hash表6.结合代码和抽象图再一次理解二.代码编写:以下代码有一个BUGclass Solution { public: int minMutation(string startGene, string endGene, vectorstring bank) { unordered_setstringvis;//判断是否遍历 unordered_setstringhash(bank.begin(),bank.end());//bankhash快速判断是否存在 string changeAGCT; if(startGeneendGene)return 0;//边界情况 if(!hash.count(endGene))return -1; queuestringq;//队列实现宽搜 q.push(startGene); vis.insert(startGene); int ret0; while(q.size()) { ret; int szq.size(); while(sz--) { string sq.front(); q.pop(); for(int i0;i8;i)//一字符串的8个位置 { for(int j0;j4;j) { s[i]change[j];//已经将原来的字符串改坏了,所以我们使用tmp修改 if(hash.count(s)!vis.count(s)) { if(sendGene)return ret; else q.push(s),vis.insert(s); } } } } } return -1; } };正确代码编写:class Solution { public: int minMutation(string startGene, string endGene, vectorstring bank) { unordered_setstringvis;//判断是否遍历 unordered_setstringhash(bank.begin(),bank.end());//bankhash快速判断是否存在 string changeAGCT; if(startGeneendGene)return 0;//边界情况 if(!hash.count(endGene))return -1; queuestringq;//队列实现宽搜 q.push(startGene); vis.insert(startGene);//哈希表标记已经搜索过的状态 int ret0; while(q.size())//BFS { ret; int szq.size(); while(sz--) { string sq.front(); q.pop(); for(int i0;i8;i)//一字符串的8个位置 { string tmps;//防止原字符串被污染 for(int j0;j4;j) { tmp[i]change[j];//已经将原来的字符串改坏了,所以我们使用tmp修改 if(hash.count(tmp)!vis.count(tmp))//在bank里面存在,并且没有遍历过 { if(tmpendGene)return ret;//相等就返回步数 else q.push(tmp),vis.insert(tmp);//BFS不相等就继续入队改变 } } } } } return -1; } };