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