LeetCode 433. 最小基因变化

题目描述

433. 最小基因变化

解法：双向 BFS

我们知道双向 BFS 最大的特点就是知道起点，知道终点，两头向中间扩散。那么这道题使用双向 BFS 再合适不过，如果你已经做过 752. 打开转盘锁 ，这道题其实是同理的：打开转盘锁因为限定了 deads 而必须在扩散过程中剪枝，而这道题刚好反过来，只有 bank 中的才可以扩散

class Solution {
public:int minMutation(string start, string end, vector& bank) {set validate;set q1;set q2;set visited;int step = 0;for(auto s: bank) validate.insert(s);if (validate.count(end) == 0) return -1;q1.insert(start);q2.insert(end);const char table[4] = {'A', 'C', 'G', 'T'};while(!q1.empty() && !q2.empty()){if (q1.size() > q2.size()){// 交换 q1 和 q2set temp = q1;q1 = q2;q2 = temp;} set tmp;for(auto cur: q1){if(q2.count(cur)) return step;visited.insert(cur);for (int i = 0; i < cur.size(); i++){for (int j = 0; j < 4; j++){string s = cur;// if (s[i] == table[j]) continue;s[i] = table[j];if (validate.count(s) == 0 || visited.count(s)) continue;tmp.insert(s);}}}step++;q1 = q2;q2 = tmp;}return -1;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！