【BFS最短路问题】最小基因变化

433. 最小基因变化

433. 最小基因变化

​ 基因序列可以表示为一条由 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 == 8
• end.length == 8
• 0 <= bank.length <= 10
• bank[i].length == 8
• start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

解题思路：边权为一的最短路问题 -> bfs解决

​ 这道题其实刷题量少的话是比较难解决的，因为其实这道题是关于图论知识的边权为一的最短路径问题，之所以可以转化为这种思路，我们得先理解题意，题目说的是 start 变成 end，其中每一步有效变化都得是 bank 数组中的字符串才行。所以如下图所示，这是 start 变化一个字符后的结果，它是一个 bank 中的字符串，然后将其作为一个新的起点继续进行变化直到结果为 end 为止：

​ 而每一步变化，其实可以看作是图的边权为一，而变化的每个结果，都可以看作是一个节点，那就可以抽象成下图的情况：

​ 转化为这种最短路问题之后，其实就可以使用 bfs 来解决问题了，大体思路和 1926. 迷宫中离入口最近的出口 是类似的，只不过这道题的细节要多一些！具体细节有如下几点：

1. 使用哈希表 bank_hash 来存储 bank 数组中的基因序列，便于快速索引。
2. 使用哈希表 used 来存储已经枚举过的基因序列，方便去重，提高效率。
3. 只需要将符合要求的变化结果添加到队列中即可。
4. 枚举所有的变化情况很简单，就是用两个 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;
    }
};