Word Ladder II

题目描述

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) 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"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

解题方法

依然是BFS, 但是这里要找到所有的最短路径，就不能直接退出，并且也不能立刻从字典里删去用过的word, 因为这一层的其他word也有可能以它为下一个neighbour, 所以要在BFS的一层node都结束后再从字典里删去 用过的数。

并且要求能够最后重建路径，所以我们用一个hashtable来存每个word的prev是什么，这样才可以重建路径。

Solution

memory limit exceeded....

from collections import deque
from string import ascii_lowercase


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

        level = 1
        curLevelNum = 1
        nextLevelNum = 0

        prevHash = {}
        prevHash[beginWord] = None

        queue = deque()
        queue.append((beginWord, level))
        wordlist.remove(beginWord)

        found = False
        while queue:
            curWord, curLevel = queue.popleft()
            curLevelNum -= 1

            if curWord == endWord:
                found = True

            removeArr = []
            ns = self.getNeighbours(curWord, wordlist)
            for word in ns:
                queue.append((word, curLevel + 1))
                nextLevelNum += 1
                removeArr.append(word)
                if word in prevHash:
                    if curWord not in prevHash[word]:
                        prevHash[word].append(curWord)
                else:
                    prevHash[word] = [curWord]

            if curLevelNum == 0:
                for w in removeArr:
                    wordlist.remove(w)
                curLevelNum = nextLevelNum
                nextLevelNum = 0

                if found:
                    results = []
                    self.getPathes(results, beginWord, endWord, prevHash)
                    return results

        return [[]]

    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

    def getPathes(self, results, beginWord, endWord, prevHash):

        queue = deque()
        queue.append((endWord, [endWord]))

        while queue:
            cur, path = queue.popleft()
            if cur == beginWord:
                results.append(path[::-1])
            else:
                for pre in prevHash[cur]:
                    path.append(pre)
                    newPath = list(path)
                    queue.append((pre, newPath))
                    path.pop()

    // another方法
    def getPathes(self, results, beginWord, curr, prevHash, curList):
        if curr == beginWord:
            newList = list(curList)
            newList.reverse()
            results.append(newList)
        else:
            for parent in prevHash[curr]:
                curList.append(parent)
                self.getPathes(results, beginWord, parent, prevHash, curList)
                curList.pop()

优化的可以过code

def buildpath(path, word):
            if len(prevMap[word])==0:
                path.append(word); currPath=path[:]
                currPath.reverse(); result.append(currPath)
                path.pop();
                return
            path.append(word)
            for iter in prevMap[word]:
                buildpath(path, iter)
            path.pop()

        result=[]
        prevMap={}
        length=len(start)
        for i in dict:
            prevMap[i]=[]
        candidates=[set(),set()]; current=0; previous=1
        candidates[current].add(start)
        while True:
            current, previous=previous, current
            for i in candidates[previous]: dict.remove(i)
            candidates[current].clear()
            for word in candidates[previous]:
                for i in range(length):
                    part1=word[:i]; part2=word[i+1:]
                    for j in 'abcdefghijklmnopqrstuvwxyz':
                        if word[i]!=j:
                            nextword=part1+j+part2
                            if nextword in dict:
                                prevMap[nextword].append(word)
                                candidates[current].add(nextword)
            if len(candidates[current])==0: return result
            if end in candidates[current]: break
        buildpath([], end)
        return result

Reference