力扣433. 最小基因变化

本文介绍: 力扣、广度优先搜索、哈希表

广度优先搜索

思路：
- 经过分析可知，基因 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<string>& bank) {
        if (startGene == endGene) {
            return 0;
        }

        std::unordered_set<std::string> bank_map;
        for (auto & s : bank) {
            bank_map.emplace(s);
        }
        if (0 == bank_map.count(endGene)) {
            return -1;
        }

        std::unordered_set<std::string> visited;
        char keys[4] = {'A', 'C', 'G', 'T'};
        std::queue<std::string> 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;
    }
};

原文地址:https://blog.csdn.net/N_BenBird/article/details/135491825

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_68011.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。