力扣433. 最小基因变化

发布时间:2024年01月10日

广度优先搜索

  • 思路:
    • 经过分析可知,基因 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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。