【面试经典 150 | 图的广度优先搜索】最小基因变化

本文主要是介绍【面试经典 150 | 图的广度优先搜索】最小基因变化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：广搜
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【图】【广度优先搜索】

题目来源

433. 最小基因变化

解题思路

方法一：广搜

思路

经过分析可知，题目要求将一个基因序列 A 变化成另一个基因序列 B，需要满足以下条件：

序列 A 和序列 B 之间只有一个字符不同；
变化字符只能从 ‘A’、‘C’、‘G’、‘T’ 中进行选择；
变换后的序列 B 一定要在字符串数组 bank 中。

根据以上规则，我们可以尝试所有合法的基因变换，并找到最小的变换次数。为此，我们可以使用广度优先搜索尝试所有基因变换。队列的第一层放置的是 start 基因，第二层放置的是与第一层对比只改变一个字符的基因，第三层放置的是与第二层对比只改变一个字符的基因…

每改变一位字符得到一个不同的基因都需要判断是否是有效的，还需要判断是否是已经出现过的字符。对于有效的以及没有出现过的基因变换，需要增加到队列中。

一些特判情况：

如果 start 和 end 相等，则直接返回 0；
如果最终的基因序列不在 bank 中，则无法进行有效变换，直接返回 -1。

代码

class Solution {
public:int minMutation(string start, string end, vector<string>& bank) {unordered_set<string> cnt;      // 存放基因库中的基因unordered_set<string> visited;  // 存放被访问过的基因char keys[4] = {'A', 'T', 'C', 'G'};for(auto &str : bank){cnt.insert(str);}// 去除一些特殊情况if(start == end){return 0;}// end 基因不在基金库中，直接返回 -1if(cnt.count(end) == 0){return -1;}queue<string> q;q.push(start);visited.insert(start);int step = 1;while(!q.empty()){int sz = q.size();int i, j, k;for(i = 0; i < sz; ++i){ // 更改当前层的所有基因string now = q.front(); q.pop();for(j = 0; j < 8; ++j){for(k = 0; k < 4; ++k){if(keys[k] != now[j]){  // 改成不同的字符string next = now;next[j] = keys[k];// 有效的并且没有被访问过if(!visited.count(next) && cnt.count(next)){if(next == end){    // 变成 end 了，直接返回return step;}q.push(next);visited.insert(next);}}}}}++step;}return -1;}
};

复杂度分析

时间复杂度： $\times n \times m)$ ， $n$ 为基因序列的长度， $m$ 为数组 bank 的长度。对于队列中的每个合法的基因序列每次都需要计算 $\times n$ 种变化，在这里 $C = 4$ ；队列中最多有 $m$ 个元素，因此时间复杂度为 $\times n \times m)$ 。