---

题目链接：

433. 最小基因变化

---

题目描述：

---

解法

先看懂题目

先把这个问题转化：图论问题

边权为1的最短路问题。

为什么可以这么想？！

因为每次一步，最终目标也有。

---

C++ 算法代码：

class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {// 使用哈希集合存储已访问的基因序列unordered_set<string> vis; // 将基因库转换为哈希集合，方便快速查找unordered_set<string> hash(bank.begin(), bank.end()); // 可能的基因变化字符string change = "ACGT"; // 如果起始基因和目标基因相同，直接返回0if (startGene == endGene)return 0;// 如果目标基因不在基因库中，直接返回-1if (!hash.count(endGene))return -1;// 使用BFS队列queue<string> q;q.push(startGene);vis.insert(startGene);int ret = 0;  // 记录突变次数while (q.size()) {ret++;  // 每处理完一层，突变次数加1int sz = q.size();  // 当前层的节点数// 处理当前层的所有节点while (sz--) {string t = q.front();q.pop();// 尝试改变每个位置的字符for (int i = 0; i < 8; i++) {string tmp = t;  // 创建临时副本，避免修改原字符串// 尝试将当前位置的字符变为A/C/G/Tfor (int j = 0; j < 4; j++) {tmp[i] = change[j];// 如果变化后的序列在基因库中且未被访问过if (hash.count(tmp) && !vis.count(tmp)) {// 找到目标基因，返回当前突变次数if (tmp == endGene)return ret;// 将新序列加入队列，并标记为已访问q.push(tmp);vis.insert(tmp);}}}}}// 如果队列为空仍未找到目标基因，返回-1return -1;}
};