【05-07】力扣每日一题

明天是母亲节，记得给自己的妈妈送上祝福，当然父母希望的是陪伴，能与妈妈一起吃顿饭那是最好不过的了。

题目内容

题目链接，433. 最小基因变化，题目截图如下：

题目分析

首先我们还是按照惯例，说一下题目大意。题目的意思很明确，给你一个start字符串和一个end字符串，然后需要你将start字符串变成end字符串，需要注意的是每次我们只能变换一个字符，并且字符串由A、G、T、C所组成，每次修改只能从这四个中选择。并且每次修改之后的字符串要出现在bank中。

其实读完题目之后我们的思路就十分明确了，我们可以使用广度优先搜索，也就是BFS。因为我们每次需要修改一个字符以达到end，而每个字符都有修改的机会，那么我们可以这样做，创建一个队列，首先将start入队，然后每次拿出来的是修改一个字符之后的结果，需要注意的是，我们修改字符之后需要判断修改完之后的字符是否在bank里，如果不在bank里，那么此次修改就无效，如果在bank里。我们需要判断这种修改有没有尝试过，如果尝试过那么也是无效的修改，如果既在bank里有没有尝试过，那么我们就将该修改入队，因为这种修改是有效的，一直到我们的修改是end，我们就返回我们的步长。如果循环结束了都没有返回结果，那我们就返回-1因为无法实现从start到end。

当然有人可能会说，凭什么第一次找到end的时候走的步数就是我们的最小变化次数呢？我们可以这样想，因为BFS是广度优先遍历，每次遍历都是在找修改一次之后合法的字符串，也就是说，我们第一次遍历是找到修改一次并且符合要求的字符串，第二次遍历是将上述一次遍历符合要求的字符串再去修改，找到符合要求的，所以我们每一步都是字符串修改一个字符的结果，那么只要找到了end，那么步长就是最小的。

如果上面的你没听懂可以直接去看下面的代码，我想看代码是最直接的方式。

代码实现

代码实现如下，不过需要注意的是，我在这里吃了个大亏，因为c++使用指针来创建数组的时候，是不会给你初始化的，我开始以为初始化为0，所以指针创建好数组之后就没有管，但是最后老是错，终于我发现需要将指针创建的数组做初始化，引以为戒！

class Solution {
private:
    unordered_map<string,int> map;
public:
    int minMutation(string start, string end, vector<string>& bank) {
        int n = bank.size();
        // 特殊情况特殊处理
        for(int i = 0;i<n;i++){
            map.insert({bank[i],i});
        }
        if(n==0 || map.find(end)==map.end()){
            return -1;
        }
        if(start==end){
            return 0;
        }
        char direction[4] = {'A','C','G','T'};
        // 记录是否访问过
        int *visted = new int[n];
        for(int i = 0;i<n;i++){
            visted[i] = 0;
        }
        queue<string> q;
        q.push(start);
        int res = 1;
        while(!q.empty()){
            int nn = q.size();
            for(int k = 0;k<nn;k++){
                string cur = q.front();
                q.pop();
                for(int i = 0;i<8;i++){
                    // 对每个位置进行修改
                    for(int j = 0;j<4;j++){
                        if(cur[i]!=direction[j]){
                            string tmp = cur;
                            tmp[i] = direction[j];
                            // 要是在bank里 并且没访问过
                            if(map.find(tmp)!=map.end() && visted[map.at(tmp)]==0){
                                if(tmp==end){
                                    // 直接找到
                                    return res;
                                }
                                // 放入队列 并且设置为访问过的
                                q.push(tmp);
                                visted[map.at(tmp)] = 1;
                            }
                        }
                    }
                }
            }
            res++;
        }
        return -1;
    }
};