13.Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.

2. Each transformed word must exist in the word list.

Note:

• Return 0 if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

• You may assume no duplicates in the word list.

• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Solution : (BFS)

Approach: Add all words in the dictionary to a set. Perform BFS by searching all words of next-level present in set. If word matches end word then return Else Insert into queue Remove the word from set Increase the level

class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string> &wordList)
    {

        unordered_set<string> s;
        queue<string> q;
        for (int i = 0; i < wordList.size(); i++)
        {
            s.insert(wordList[i]);
        }

        if (s.find(endWord) == s.end())
        {
            return 0;
        }

        q.push(beginWord);
        int cvLen = 1;
        while (!q.empty())
        {

            int sz = q.size();
            while (sz > 0)
            {
                string temp = q.front();
                q.pop();

                for (int i = 0; i < temp.length(); i++)
                {
                    char org = temp[i];
                    for (int j = 0; j < 26; j++)
                    {
                        if (temp[i] - 97 != j)
                        {
                            temp[i] = j + 97;
                            if (s.find(temp) != s.end())
                            {
                                if (temp == endWord)
                                {
                                    return cvLen + 1;
                                }
                                else
                                {
                                    q.push(temp);
                                    s.erase(s.find(temp));
                                }
                            }
                        }
                    }
                    temp[i] = org;
                }

                sz--;
            }
            cvLen++;
        }
        return 0;
    }
};

Time Complexity: O(n^2 * 26 * w) n = length of string w = length of word dictionary