Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of the 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 that beginWord is not a transformed word.
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 is not the same as endWord.
- All the words in wordList are unique.
Examples:
Input: ["hit","cog","dot","dog","lot","log","cog"], "hit", "cog"
Output: 5
Explanation: One possible transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", and another possible transformation is "hit" -> "hot" -> "lot" -> "log" -> "cog".
Solutions
Breadth-First Search
The solution uses a breadth-first search (BFS) approach to find the shortest transformation sequence. It starts with the beginWord and explores all possible transformations by changing one letter at a time. The transformed words are added to a queue and the process continues until the endWord is found or the queue is empty.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
queue = deque([[beginWord, 1]])
while queue:
word, length = queue.popleft()
if word == endWord:
return length
for i in range(len(word)):
for j in range(26):
next_word = word[:i] + chr(97 + j) + word[i + 1:]
if next_word in word_set:
queue.append([next_word, length + 1])
word_set.remove(next_word)
return 0Follow-up:
What if the word list is very large and we need to optimize the solution for memory usage?
