You are given two words, beginWord and endWord, and a dictionary of words wordList. Your task is to find 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 given wordList.
Return the length of the shortest transformation sequence. If there is no such transformation sequence, return 0.
Example:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the wordList.
You may assume beginWord and endWord are non-empty and are not the same.
from collections import deque
class Solution:
@staticmethod
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
wordSet = set(wordList)
queue = deque([(beginWord, 1)])
visited = set()
while queue:
word, level = queue.popleft()
if word == endWord:
return level
for i in range(len(word)):
for char in 'abcdefghijklmnopqrstuvwxyz':
newWord = word[:i] + char + word[i+1:]
if newWord in wordSet and newWord not in visited:
queue.append((newWord, level + 1))
visited.add(newWord)
return 0import codewars_test as test
# TODO Write tests
import solution # or from solution import example
# test.assert_equals(actual, expected, [optional] message)
@test.describe("Example")
def test_group():
@test.it("Test Case 1")
def test_case_1():
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
test.assert_equals(Solution.ladderLength(beginWord, endWord, wordList), 5)
@test.it("Test Case 2")
def test_case_2():
beginWord = "a"
endWord = "c"
wordList = ["a", "b", "c"]
test.assert_equals(Solution.ladderLength(beginWord, endWord, wordList), 2)
@test.it("Test Case 3")
def test_case_3():
beginWord = "red"
endWord = "tax"
wordList = ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"]
test.assert_equals(Solution.ladderLength(beginWord, endWord, wordList), 4)
@test.it("Test Case 4")
def test_case_4():
beginWord = "hot"
endWord = "dog"
wordList = ["hot", "dog"]
test.assert_equals(Solution.ladderLength(beginWord, endWord, wordList), 0)
@test.it("Test Case 5")
def test_case_5():
beginWord = "a"
endWord = "z"
wordList = ["b"]
test.assert_equals(Solution.ladderLength(beginWord, endWord, wordList), 0)