LC 0127 [H] Word Ladder - ALawliet/algorithms GitHub Wiki
use a set so we can lookup and remove used words
shortest path BFS where the neighbors are swapping the char at the index and trying out every other letter in the alphabet
# ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
ALPHABET = string.ascii_lowercase
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
wordList = set(wordList) # faster lookup and acts as visited set
Q = deque([ [beginWord, 1] ])
while Q:
word, path_len = Q.popleft()
if word == endWord:
return path_len
for i in range(len(word)):
for c in ALPHABET:
neighbor_word = word[:i] + c + word[i+1:]
if neighbor_word in wordList:
wordList.remove(neighbor_word)
Q.append( [neighbor_word, path_len + 1] )
return 0