class Solution {
public:
   int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
      //bidirectional BFS
      queue<string> q1, q2;
      unordered_set<string> visited1, visited2;
      unordered_set<string> words;
      for (auto& word : wordList)words.insert(word);
      if(words.find(endWord) == words.end())return 0;
      q1.push(beginWord);
      q2.push(endWord);
      int layer1 = 0, layer2 = 0;
      while (q1.size() && q2.size())
      {
         int len1 = q1.size(), len2 = q2.size();
         ++layer1;
         for (int i = 0; i < len1; ++i)
         {
            auto curr = q1.front();
            q1.pop();
            if (visited1.find(curr) != visited1.end())continue;
            if (visited2.find(curr) != visited2.end())return layer1 + layer2 - 1;
            visited1.insert(curr);
            for (auto& next : adj(curr, words))
               q1.push(next);
         }
         ++layer2;
         for (int i = 0; i < len2; ++i)
         {
            auto curr = q2.front();
            q2.pop();
            if (visited2.find(curr) != visited2.end())continue;
            if (visited1.find(curr) != visited1.end())return layer1 + layer2 - 1;
            visited2.insert(curr);
            for (auto& next : adj(curr, words))
               q2.push(next);
         }
      }
      return 0;
   }

private:
   vector<string> adj(string word, unordered_set<string>& list)
   {
      vector<string> res;
      for (int i = 0; i < word.size(); ++i)
      {
         string tmp = word;
         for (int j = 0; j < 26; ++j)
         {
            char c = 'a' + j;
            if (c == word[i])continue;
            tmp[i] = c;
            if (list.find(tmp) != list.end())
               res.push_back(tmp);
         }
      }
      return res;
   }
};