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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param start string字符串 
     * @param end string字符串 
     * @param bank string字符串vector 
     * @return int整型
     */
    bool check(string str_1, string str_2)
    {
        int res = 0;
        for(int i=0; i<str_1.size(); ++i)
        {
            if(str_1[i]!=str_2[i])
                ++res;

            if(res>1)
                return false;
        }

        return res==1;
    }

    int minMutation(string start, string end, vector<string>& bank) {
        // write code here
        // 这不是跟 NB8 牛群最短移动序列 差不多吗，这就是简单题了？字符串长度倒是固定8个字符
        // 哈希表+广度优先搜索

        unordered_set<string> u_s(bank.begin(),bank.end());
        if(u_s.count(end)==0)
            return -1;
        if(u_s.count(start))
            u_s.erase(start);

        queue<string> q;
        q.emplace(start);
        int ans = -1;

        while(!q.empty())
        {
            ++ans;
            int len = q.size();
            for(int i=0; i<len; ++i)
            {
                string str = q.front();
                q.pop();

                if(str==end)
                    return ans;

                for(auto it=u_s.begin(); it!=u_s.end(); )
                {
                    if(check(str,*it))
                    {
                        q.emplace(*it);
                        it=u_s.erase(it);
                    }
                    else
                        ++it;
                }
            }
        }

        return -1;
    }
};