Simple BFS with memorization
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
#time complexity: O(L^(len(word)*26))
#space complexity: O(N)
res = 0
Q = collections.deque()
Q.append(beginWord)
Set = set(wordList)
if endWord not in Set:
return 0
while(Q):
res += 1
n = len(Q)
for i in range(n):
word = Q.popleft()
for j in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
word_copy = word[:j] + ch + word[j+1:]
if str(word_copy) == endWord:
return res + 1
if str(word_copy) in Set:
Q.append(str(word_copy))
Set.remove(str(word_copy))
return 0