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

Constraints:

• `1 <= beginWord.length <= 10`
• `endWord.length == beginWord.length`
• `1 <= wordList.length <= 5000`
• `wordList[i].length == beginWord.length`
• `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters.
• `beginWord != endWord`
• All the words in `wordList` are unique.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 `````` ``````from collections import defaultdict, deque class Solution: def __init__(self): self.len = 0 self.all_d = defaultdict(list) def get_inter_word(self, word: str, i: int) -> str: return word[:i] + "*" + word[i+1:] def visit_word(self, q: deque, visited: dict, others_visited:dict) -> Optional[int]: for _ in range(len(q)): current_word = q.popleft() for i in range(self.len): for word in self.all_d[self.get_inter_word(current_word, i)]: if word in others_visited: return visited[current_word] + others_visited[word] if word not in visited: visited[word] = visited[current_word] + 1 q.append(word) return None def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if (not beginWord or not endWord or not wordList or endWord not in wordList): return 0 self.len = len(beginWord) for word in wordList: for i in range(self.len): self.all_d[self.get_inter_word(word, i)].append(word) q_begin = deque([beginWord]) q_end = deque([endWord]) visited_begin = {beginWord: 1} visited_end = {endWord: 1} ans = None while q_begin and q_end: if len(q_begin) <= len(q_end): ans = self.visit_word(q_begin, visited_begin, visited_end) else: ans = self.visit_word(q_end, visited_end, visited_begin) if ans: return ans return 0``````