leetcode433 最小基因变化

题目

最小基因变化

分析

解法：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;
    }
};