题解 | #基因变异最小次数#

#include <unordered_set>
#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param start string字符串 
     * @param end string字符串 
     * @param bank string字符串vector 
     * @return int整型
     */
    int minMutation(string start, string end, vector<string>& bank) {
        // write code here
        unordered_set<string> visited, bankset;
        queue<string> qu;
        qu.push(start);
        visited.insert(start);
        for (int i = 0; i < bank.size(); i++) {
            bankset.insert(bank[i]);
        }

        int operation = 0;
        vector<string> trans{"A", "C", "G", "T"};
        while (!qu.empty()) {
            int size = qu.size();
            // 对这一层的所有进行每种可能的变换
            for (int i = 0; i < size; i++) {
                string tmp = qu.front();
                qu.pop();
                // 判断是否和end相等
                if (end == tmp) {
                    return operation; 
                }
                // 对每一个位置尝试四种变换
                for (int j = 0; j < tmp.size(); j++) {
                    for (int k = 0; k < 4; k++) {
                        string next = tmp;
                        next.replace(j, 1, trans[k]);
                        if (bankset.count(next) && !visited.count(next)) {
                            qu.push(next);
                            visited.insert(next);
                        }
                    }
                }
            }
            // 这一层算一次操作
            operation++;

        }
        return -1;
    }
};