题解 | #牛群最短移动序列#

#include <string>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param beginWord string字符串 
     * @param endWord string字符串 
     * @param wordList string字符串vector 
     * @return int整型
     */
    
    // 检测两个字符串有多少个不同的字符
    bool check(string str_1, string str_2)
    {
        if(str_1.size()!=str_2.size())
            return false;
        
        int len = str_1.size();
        int res = 0;
        for(int i=0; i<len; ++i)
        {
            if(str_1[i]!=str_2[i])
                ++res;
        }

        return res==1;
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // write code here

        // 哈希 + 广度优先搜索
        unordered_set<string> u_s(wordList.begin(),wordList.end());

        if(u_s.count(endWord)==0)
            return 0;

        // 将u_s中与beginWord一样的字符串删除
        if(u_s.count(beginWord))
            u_s.erase(beginWord);

        queue<string> q;
        q.emplace(beginWord);

        while(!q.empty())
        {
            int len = q.size();
            ++ans;

            for(int i=0; i<len; ++i)
            {
                string str= q.front();
                q.pop();
                
                if(str==endWord)
                    return ans;
                    
                // 从字典中找到与q.front()一字之差的字符串
                for(auto it=u_s.begin(); it!=u_s.end(); )
                {
                    if(check(str, *it))
                    {
                        q.emplace(*it);
                        // u_s中删除这个字符串，避免重复利用
                        u_s.erase(it);
                        // 这里需要将it重新定义为u_s.begin()，否则产生段错误，it都被删了哪还有it
                        it = u_s.begin();
                        continue;
                    }
                    ++it;
                }
            }
        }

        return 0;
    }

private:
    int ans = 0;
};