哈希+广度优先搜索

#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);                         it = u_s.erase(it);                         // q.emplace(*it);                         // // u_s中删除这个字符串，避免重复利用                         // u_s.erase(it);                         // // 这里需要将it重新定义为u_s.begin()，否则产生段错误，it都被删了哪还有it                         // it = u_s.begin();                         // continue;                     }                     else                         ++it;                 }             }         }          return 0;     }  private:     int ans = 0; };