Word Ladder

题目描述

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time Each intermediate word must exist in the word list For example,

Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

解题方法

求最短路径一般是用BFS的方法，这里就是不断的BFS搜查当前word的neighbours（在wordList里的)， 如果遍历字典里的 所有word，那么会随着字典的变大而时间复杂度太大，我们可以用26个字母去替换，就得到固定的时间复杂度。

注意点

  • 一开始要将endWord加入到wordList里，这样最后达到的时候好判断
  • 只要已经是endWord了就可以立刻返回，因为只要求最小的长度，BFS最先得到的必然是最小长度
  • BFS将neighbours加入到queue之后要将它们从wordList中删去，不然会得到重复的loop

Solution

from collections import deque
from string import ascii_lowercase

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :rtype: int
        """
        if not beginWord or not endWord or not wordList:
            return
        wordList.add(endWord)

        level = 1
        queue = deque()
        queue.append((beginWord, level))
        while queue:
            curWord, curLevel = queue.popleft()
            if curWord == endWord:
                return curLevel

            removeArr = []
            ns = self.getNeighbours(curWord, wordList)
            for word in ns:
                queue.append((word, curLevel + 1))
                removeArr.append(word)

            for w in removeArr:
                wordList.remove(w)

        return 0

    def getNeighbours(self, curr, wordList):
        neighbours = []
        for i in range(len(curr)):
            for c in ascii_lowercase:
                n = curr[:i] + c + curr[i+1:]
                if n in wordList and n != curr:
                    neighbours.append(n)

        return neighbours

Reference