今天和大家聊的问题叫做 最小基因变化，我们先来看题面：https://leetcode-cn.com/problems/minimum-genetic-mutation/
一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。例如，基因序列由"AACCGGTT" 变化至 "AACCGGTA" 即发生了一次基因变化。与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。注意：起始基因序列默认是合法的，但是它并不一定会出现在基因库中。如果一个起始基因序列需要多次变化，那么它每一次变化之后的基因序列都必须是合法的。假定起始基因序列与目标基因序列是不一样的。
示例
示例 1： start: "AACCGGTT" end: "AACCGGTA" bank: ["AACCGGTA"] 返回值: 1 示例 2： start: "AACCGGTT" end: "AAACGGTA" bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"] 返回值: 2 示例 3： start: "AAAAACCC" end: "AACCCCCC" bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"] 返回值: 3
解题
思路 ：bfs将每个单词用hash表存起来作为一个字典判断end在不在里面，不在则直接返回-1将start入队对每一层的每一个单词，将它的每一位改成ATCG四个字母，改变之后如果单词为end就返回bfs树的层数，如果不为end就判断是否在字典里，在字典里就入队。
class Solution { private: unordered_set<string> st; bool find_end(string& str, string& end, queue<string>& que) { vector<char> next({'A', 'C', 'T', 'G'}); for (int m = 0; m < str.size(); m++) { string new_str = str; for (int n = 0; n < 4; n++) { new_str[m] = next[n]; if (new_str == end) { return true; } if (st.count(new_str)) { que.push(new_str); st.erase(new_str); } } } return false; } public: int minMutation(string start, string end, vector<string>& bank) { st = unordered_set<string>(bank.begin(), bank.end()); if (st.count(end) == 0) { return -1; } queue<string> que; que.push(start); int res = 0; while (!que.empty()) { res++; int size = que.size(); for (int i = 0; i < size; i++) { string str = que.front(); que.pop(); if (find_end(str, end, que)) { return res; } } } return -1; } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
