LeetCode link: 127. Word Ladder
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
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList. 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.
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.
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.
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English letters.beginWord != endWord- All the words in
wordListare unique.
This problem is hard. Before solving this problem, you can do the following problem first:
The word transformation sequence problem can be abstracted into a graph theory problem. And it is an undirected graph:
-
As shown in the figure above, Breadth-First Search can be thought of as visiting vertices in rounds and rounds. Actually, whenever you see a question is about getting
minimum numberof something of a graph,Breadth-First Searchwould probably help. -
Breadth-First Searchemphasizes first-in-first-out, so a queue is needed.
Breadth-First Searcha graph means traversing from near to far, fromcircle 1tocircle N. Eachcircleis a round of iteration.- So through
Breadth-First Search, when a word matchesendWord, the game is over, and we can return the number of circle as a result.
- Time:
O((26 * end_word.length) * N). - Space:
O(N).
from collections import deque
class Solution:
def ladderLength(self, begin_word: str, end_word: str, word_list: List[str]) -> int:
words = set(word_list)
if end_word not in words:
return 0
if begin_word == end_word:
return 1
queue = deque([begin_word])
if begin_word in words:
words.remove(begin_word)
result = 0
while queue:
size = len(queue)
result += 1
for i in range(size):
current_word = queue.popleft()
for word in one_letter_changed_words(current_word):
if word == end_word:
return result + 1
if word in words:
queue.append(word)
words.remove(word)
return 0
def one_letter_changed_words(word):
words = []
for i in range(len(word)):
for letter in 'abcdefghijklmnopqrstuvwxyz':
if letter != word[i]:
words.append(word[:i] + letter + word[i + 1:])
return words// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!# Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!// Welcome to create a PR to complete the code of this language, thanks!