Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

1.Every adjacent pair of words differs by a single letter.

2.Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

3. sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

C++

#include <bits/stdc++.h>
using namespace std;

int ladderLength(string start, string end, vector<string> &word)
{
    int level = 1;
    unordered_set<string> st(word.begin(), word.end());
    queue<string> q;
    q.push(start);
    while (!q.empty())
    {
        int size = q.size();
        while (size--)
        {
            auto temp = q.front();

            q.pop();
            if (temp == end)
            {

                return level;
            }
            st.erase(temp);
            for (int k = 0; k < temp.size(); k++)
            {
                char ch = temp[k];
                for (int i = 0; i < 26; i++)
                {
                    temp[k] = i + 'a';
                    if (st.count(temp))
                    {
                        q.push(temp);
                    }
                }
                temp[k] = ch;
            }
        }
        level++;
    }
    return 0;
}

int main()
{
    string beginWord = "hit";
    string endWord = "cog";
    vector<string> wordList = {"hot", "dot", "dog",
                               "lot", "log", "cog"};

    cout << ladderLength(beginWord, endWord, wordList);

    return 0;
}