127. Word Ladder
https://leetcode.com/problems/word-ladder/
Python
- BFS with deuplicate remove
from collections import deque
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if beginWord == endWord:
return 1
queue = deque()
queue.append(beginWord)
candidates = set(wordList)
candidates.add(beginWord)
result = 1
while queue:
for i in range(len(queue)):
word = queue.popleft()
if word not in candidates:
continue
candidates.remove(word)
if word == endWord:
return result
for i in range(len(word)):
for char in string.ascii_letters[:26]:
temp_word = word[:i] + char + word[i+1:]
if temp_word in candidates:
queue.append(temp_word)
result += 1
return 0