**Description**

Given two words beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that:

- Only one letter can be changed at a time.
- Each transformed word must exist in the word list.
- Return 0 if there is no such transformation sequence.

**Example 1**

Input

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

Output

```
5
# 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`

**Approach**

BFS-algorithm is required to solve this problem since we are to return the shortest transformation sequence from beginWord to endWord. However, this problem is not just about BFS but also about pre-processing inputs by brute-forcing every possible options which match the pair in wordList.

**Solution (Python) **

```
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
qu = [(beginWord, 1)]
size = len(beginWord)
visit = {}
permute = {}
for word in wordList:
visit[word] = False
for word in wordList:
for i in range(size):
op = word[:i] + '*' + word[i+1:]
if op not in permute:
permute[op] = [word]
else:
permute[op].append(word)
while qu:
cur, cnt = qu.pop()
visit[cur] = True
if cur == endWord:
return cnt
for i in range(size):
op = cur[:i] + '*' + cur[i+1:]
if op not in permute:
permute[op] = []
else:
for poss in permute[op]:
if visit[poss] == False:
qu.insert(0, [poss, cnt+1])
return 0
```

**Result**

Runtime : 3196ms

Memory Usage : 20.5MB

Runtime Beats 6.53% of Python Submission