# C++ BFS solution with search 0(26 * word.length() ) wordList removed by step of bfs

• class Solution {
public:

``````vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
vector<vector<string>> ans;
vector<string> path;
vector <string> next;

vector< pair<string, pair<int, int> > > bfs;
int st = 0, fin = 0, k, last = 0;

if (beginWord == "" || beginWord == endWord) return ans;
wordList.insert(endWord);
//worst case : path consist of all words
int min = wordList.size();

next.push_back(beginWord);

bfs.push_back( make_pair (beginWord, make_pair(1, -1)) );
while( st <= fin && min > bfs[st].second.first ){
if (last != bfs[st].second.first ) {
last = bfs[st].second.first;
for (int i=0; i<next.size(); i++)
wordList.erase(next[i]);
next.clear();
}

//cout<<bfs[st].first<<" "<<bfs[st].second.first<<" "<<bfs[st].second.second<<endl;

string nextWord;
beginWord = bfs[st].first;
//nextWords all set next[i], bfs[st].second.first + 1, st

for (int i=0; i<beginWord.length(); i++){
nextWord = beginWord;
for (int j=0; j<26; j++){
nextWord[i] = 'a'+ j;

auto it = wordList.find(nextWord);
if (it != wordList.end() && nextWord != beginWord ) {
next.push_back(nextWord);
fin++;
bfs.push_back( make_pair (nextWord, make_pair(bfs[st].second.first + 1, st)) );
if (nextWord == endWord){
//cout<<fin<<endl;
min = bfs[st].second.first + 1;
path.clear();
k = fin;
while(bfs[k].second.second != -1){
path.push_back( bfs[k].first );
k = bfs[k].second.second;
}
path.push_back( bfs[k].first );
//cout<<endl<<path.size()<< ": ";
reverse( path.begin(), path.end() );
// for (k = 0; k < path.size(); k++){
//     cout<<path[k]<<" ";
// }
ans.push_back(path);
}
}
}
}
st++;
}

return ans;
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.