127. Word Ladder

https://leetcode.com/problems/word-ladder/

solution

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        visited = set()
        queue = collections.deque()
        queue.append(beginWord)
        visited.add(beginWord)  # 注意防止遍历成环

        step = 0
        while queue:
            step += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                for i in range(len(node)):
                    for c in string.ascii_lowercase:
                        new_word = node[:i] + c + node[i+1:]
                        if new_word in wordList and new_word not in visited:
                            if new_word == endWord:
                                return step + 1

                            queue.append(new_word)
                            visited.add(new_word)
        return 0

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordset = set(wordList)  # hashset也是加速方法
        queue = collections.deque()
        queue.append((beginWord, 1))
        word_length = len(beginWord)
        while queue:
            word, step = queue.popleft()
            if word == endWord:
                return step
            for i in range(word_length):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in wordset:
                        wordset.remove(new_word)
                        queue.append((new_word, step+1))
        return 0

时间复杂度：O(∣wordList∣⋅26^(wordList[i])) 空间复杂度：O(∣wordList∣)

• 双向bfs

follow up

126 Word Ladder II