广度优先搜索

• 思路：
  • 经过分析可知，基因 A 突变到基因 B，需要满足以下条件：
    • 序列 A 与序列 B 只有一个字符不同；
    • 变化字符在集合中；
    • 突变后的基因 B 一定在 bank 中；
  • 尝试搜索所有合法突变的基因集合，并找到最小突变次数：
    • 如果 start 与 end 相等，没有突变，次数为 0；
    • 如果 end 不在 bank 中，则无法生成，次数为 -1；
    • 可能变化的基因集合 s 从队列中取出，根据上述突变规则，尝试所有可能变化后的基因序列；（遍历位置、字符）
    • 突变的基因 s(i) 需要合法，所以需要在 bank 集合中，可以将 bank 转成一个哈希表加速检索，合法的基因加入队列中，不合法的丢弃；
    • 同时，需要一个哈希表记录已经被检索过的基因，检索过的基因直接跳过；
    • 如果中途突变的基因与 end 基因匹配上，则搜索终止；否则，直至广度优先遍历所有可能；

  class Solution {
  public:
      int minMutation(string startGene, string endGene, vector& bank) {
          if (startGene == endGene) {
              return 0;
          }
          std::unordered_set bank_map;
          for (auto & s : bank) {
              bank_map.emplace(s);
          }
          if (0 == bank_map.count(endGene)) {
              return -1;
          }
          std::unordered_set visited;
          char keys[4] = {'A', 'C', 'G', 'T'};
          std::queue qu;
          qu.emplace(startGene);
          visited.emplace(startGene);
          int step = 1;
          while (!qu.empty()) {
              int sz = qu.size();
              for (int i = 0; i < sz; ++i) {
                  std::string cur = qu.front();
                  qu.pop();
                  for (int j = 0; j < 8; ++j) {
                      for (int k = 0; k < 4; ++k) {
                          std::string next = cur;
                          next[j] = keys[k];
                          if (visited.count(next) == 0 && bank_map.count(next)) {
                              if (next == endGene) {
                                  return step;
                              }
                              qu.emplace(next);
                              visited.emplace(next);                        
                          }
                      }
                  }
              }
              step++;
          }
          return -1;
      }
  };

   
   大作设计网站作品  网站建设设计说明  建个网站一般多少钱  合肥网站建设电话  石家庄网络推广平台  dreamweaver下载