Word Ladder.cpp

#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <queue>



using namespace std;


class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if(!wordSet.count(endWord)) return 0;
        queue<string> q{{beginWord}};
        int res = 0;
        while(!q.empty())
        {
            for(int k = q.size(); k > 0; k--)
            {
                string word = q.front();
                q.pop();
                if(word == endWord) return res+1;
                for(int i = 0; i < word.size(); i++)
                {
                    string newWord = word;
                    for(char ch = 'a'; ch <= 'z'; ch++)
                    {
                        newWord[i] = ch;
                        if(wordSet.count(newWord) && newWord != word)
                        {
                            q.push(newWord);
                            wordSet.erase(newWord);
                        }
                    }
                }
            }
            res++;
        }
        return 0;
    }
};