LeetCode刷题实战433：最小基因变化-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最小基因变化，我们先来看题面：

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;
    }
};