题目描述：

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 ‘A’、‘C’、‘G’ 和 ‘T’ 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

• 例如，“AACCGGTT” --> “AACCGGTA” 就是一次基因变化。

另有一个基因库 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’] 组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-genetic-mutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路一：关键是每变一下，必须保证变化后的序列在bank中。我们可以用广度优先搜索，用一个队列记录当前变化步骤的层数的序列，用一个访问数组记录已经访问的序列（防止出现圈）。

1. start入队，然后访问start，start出队
2. 将变化一个字母所有可能的情况加入队列。
3. 访问当前队首节点，返回到2开始循环。
4. 循环结束条件是队列为空，每次while循环一个代表又深了一层。

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> sbank;//基因库，有count()函数
        unordered_set<string> visited;//访问集合
        char keys[4]={'A','C','G','T'};//可以转变的字符
        if(start==end) return 0;
        for(auto &w:bank){
            sbank.emplace(w);
        }
        if(!sbank.count(end)) return -1;//end不在bank里直接结束。
        queue<string> qu;
        qu.emplace(start);
        visited.emplace(start);//加入队列即访问
        int step=1;//可以说是层数
        while(!qu.empty()){
            int sz=qu.size();
            for(int i=0;i<sz;++i){//遍历一层
                string curr=qu.front();
                qu.pop();
                for(int j=0;j<8;++j){//暴力变化一个单词所有可能的情况：3*8=24种
                //这里其实可以只在bank中遍历
                    for(int k=0;k<4;++k){
                        if(keys[k]!=curr[j]){
                            string next=curr;
                            next[j]=keys[k];
                            if(!visited.count(next)&&sbank.count(next)){//必须是未访问过，且在基因库中才入队访问。
                                if(next==end)   return step;
                                qu.emplace(next);
                                visited.emplace(next);//加入队列即访问
                            }
                        }
                    }
                }
            }
            ++step;//一次while循环代表广度遍历了一层
        }
        return -1;//如果无法完成此基因变化，返回 -1 。
    }
};

unordered_set里有count()函数。
访问数组

解题思路二：优化，不是暴力搜索下一层，而是只在bank中搜索下一层中的序列。

class Solution {
public:
    //字母相差为1
    bool change_1(string a,string b){
        int count = 0;
        for(int i=0;i<8;++i){
            if(a[i]!=b[i]){
                ++count;
            }
        }
        if(count==1) return true;
        return false;
    }

    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> sbank;//基因库，有count()函数
        unordered_set<string> visited;//访问集合
        if(start==end) return 0;
        for(auto &w:bank){
            sbank.emplace(w);
        }
        if(!sbank.count(end)) return -1;//end不在bank里直接结束。
        queue<string> qu;
        qu.emplace(start);
        visited.emplace(start);//加入队列即访问
        int step=1;//可以说是层数
        int n=bank.size();
        while(!qu.empty()){
            int sz=qu.size();
            for(int i=0;i<sz;++i){//遍历一层
                string curr=qu.front();
                qu.pop();
                for(int j=0;j<n;++j){//这里其实可以只在bank中遍历
                //注意局部变量为j
                    if(!visited.count(bank[j])&&change_1(curr,bank[j])){//下一层中的序列
                        if(bank[j]==end) return step;
                        qu.emplace(bank[j]);
                        visited.emplace(bank[j]);//加入队列即访问                    
                    }
                }
            }
            ++step;//一次while循环代表广度遍历了一层
        }
        return -1;//如果无法完成此基因变化，返回 -1 。
    }
};