基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
示例 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提示：
start.length == 8end.length == 80 <= bank.length <= 10bank[i].length == 8start、end和bank[i]仅由字符['A', 'C', 'G', 'T']组成
解题思路：边权为一的最短路问题 -> bfs解决
这道题其实刷题量少的话是比较难解决的，因为其实这道题是关于图论知识的边权为一的最短路径问题，之所以可以转化为这种思路，我们得先理解题意，题目说的是 start 变成 end，其中每一步有效变化都得是 bank 数组中的字符串才行。所以如下图所示，这是 start 变化一个字符后的结果，它是一个 bank 中的字符串，然后将其作为一个新的起点继续进行变化直到结果为 end 为止：
而每一步变化，其实可以看作是图的边权为一，而变化的每个结果，都可以看作是一个节点，那就可以抽象成下图的情况：
转化为这种最短路问题之后，其实就可以使用 bfs 来解决问题了，大体思路和 1926. 迷宫中离入口最近的出口 是类似的，只不过这道题的细节要多一些！具体细节有如下几点：
- 使用哈希表
bank_hash来存储bank数组中的基因序列，便于快速索引。 - 使用哈希表
used来存储已经枚举过的基因序列，方便去重，提高效率。 - 只需要将符合要求的变化结果添加到队列中即可。
- 枚举所有的变化情况很简单，就是用两个
for循环即可做到！
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
string gene = "ACGT";
unordered_set<string> used; // 存储已经枚举过的基因序列，方便去重
unordered_set<string> bank_hash(bank.begin(), bank.end()); // 存储bank中的基因序列，便于快速索引
// 边界情况处理
if(startGene == endGene) return 0;
if(bank_hash.count(endGene) == 0) return -1;
queue<string> bfs;
bfs.push(startGene);
int step = 0;
while(!bfs.empty())
{
step++; // 每一次变换则让step++即可
// 将一次变换的所有有效结果都作为新起点重复进行bfs操作
int size = bfs.size();
while(size--)
{
string front = bfs.front();
bfs.pop();
// 枚举基因序列每一位变换为ACGT每个字符后的结果
for(int i = 0; i < 8; ++i) // 8表示基因序列的长度
{
string tmp = front; // 细节，要使用临时变量而不能直接对front操作
for(int j = 0; j < 4; ++j) // 4表示组成基因序列的字符个数，即ACGT
{
tmp[i] = gene[j];
// 如果该变化结果是有效的，并且没出现过，才进行处理
if(bank_hash.count(tmp) != 0 && used.count(tmp) == 0)
{
// 如果就是最终结果，则直接返回step
if(tmp == endGene)
return step;
bfs.push(tmp);
used.insert(tmp);
}
}
}
}
}
return -1;
}
};