Hard graph part 3

Sometimes the graph problem is hard not as it is hard to solve by using a graph algorithm. It is hard as it is not easy to convert it to a graph problem.

127. Word Ladder

Word Ladder - LeetCode

C++ for bfs, critical part is this line of code

for(int i=q.size();i>0;--i) 
// DO NOT use this one as the q size will be changed.
//for(int i=0;i<q.size();++i)

BFS code is below. It can be improved by bidirectional BFS.

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> q;
        unordered_set<string> words(wordList.begin(), wordList.end());
        unordered_map<string, int> word_i;
        word_i[beginWord]=-1;
        q.push(beginWord);
        words.erase(beginWord);
        if(!words.count(endWord))return 0;
        //if(beginWord==endWord)return 1;
        int step = 0 ;
        while(!q.empty()){
            step++;
            for(int i=q.size();i>0;--i){
                string word = q.front();
                //cout<<step<<" **"<<word<<endl;
                q.pop();
                int loc = word_i[word];
                for(int j=0;j<word.length();++j){
                    if(j==loc)continue;
                    char ch = word[j];
                    for(int c='a';c<='z';++c){
                        if(c==ch)continue;
                        word[j]=c;
                        if(words.count(word)){
                            if(word==endWord)return step+1;
                            word_i[word] = j;
                            q.push(word);
                            words.erase(word);
                        }
                    }
                    word[j]=ch;
                }
            }
        }
        return 0;
        }
};