# 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.** \
&#x20;   **If word matches end word then return**\
&#x20;   **Else**\
&#x20;      **Insert into queue**\
&#x20;      **Remove the word from set**\
**Increase the level**\\

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MMZCaoQ1FivNdh8WBiO%2F-MMZI2ZxEzvjK-nAnY1Q%2FWord_Ladder_1.png?alt=media\&token=62c33375-3a04-4f5a-8342-53141b93a576)

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MMZCaoQ1FivNdh8WBiO%2F-MMZHHwcwbIIXlmy2QFN%2FWord_Ladder_2.png?alt=media\&token=bf95388d-0d12-487d-9298-17f87776f826)

```cpp
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**
