### Problem Statement#

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

• Every adjacent pair of words differs by a single letter.
• Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
• `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 1:#

``````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.
``````

#### Example 2:#

``````Input: beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList,
therefore there is no valid transformation sequence.
``````

### BFS: Iterative#

``````from collections import defaultdict, deque
from typing import List, Dict

class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

# S: O(N*M)
"""
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

defaultdict(<class 'set'>,
{'*og': {'dog', 'cog', 'log'},
'*ot': {'lot', 'hot', 'dot'},
'c*g': {'cog'},
'co*': {'cog'},
'd*g': {'dog'},
'd*t': {'dot'},
'do*': {'dog', 'dot'},
'h*t': {'hot'},
'ho*': {'hot'},
'l*g': {'log'},
'l*t': {'lot'},
'lo*': {'lot', 'log'}})
"""
seen = set()
queue = deque([beginWord])
dist = 0

# T: O(N*M^2)
# BFS Traversal
while queue:
dist += 1
for _ in range(len(queue)):
u = queue.popleft()

if u == endWord:
return dist

# T: O(M^2)
# We insert a step in the middle of the standard
# "traverse each parent's neighbors" approach.
# This intermediate step generates patterns
# for each word in the adjacency list (set) and
# then uses that pattern to get the neighbouring
# words that are one letter modification away.
for pat in self.m_patterns(u):
if v not in seen:
queue.append(v)

return 0

# T: O(N*M^2)
# S: O(N*M)
def m_adj(self, words: List[str]) -> Dict[str, set]:
"""
Loop through all of the words in the words list and
create an adjacency list (set). The key will be the
pattern and the values will be the words.
In this problem, we can move from one word to another
if the next word can be created by changing one letter.
Example. word: "hit" -> keys = ["*it", "h*t", "hi*"].
Any word that matches the previous three patterns is
a valid next step.
"""
# T: O(M)
for word in words:
# T: O(M)
patterns = set(self.m_patterns(word))
for pat in patterns: