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; } };