Word Ladder II

Question

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

• Only one letter can be changed at a time
• Each intermediate word must exist in the dictionary

Example

Given:

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note

• All words have the same length.
• All words contain only lowercase alphabetic characters.

  Thoughts

word ladder 2 word ladder 2

分析：本题主要的框架和上一题是一样，但是还要解决两个额外的问题：

1. 怎样保证求得所有的最短路径
2. 怎样构造这些路径

第一问题：

不能像上一题第二点注意那样，找到一个单词相邻的单词后就立马把它从字典里删除，因为当前层还有其他单词可能和该单词是相邻的，这也是一条最短路径，比如hot->hog->dog->dig和hot->dot->dog->dig，找到hog的相邻dog后不能立马删除，因为和hog同一层的单词dot的相邻也是dog，两者均是一条最短路径。但是为了避免进入死循环，再hog、dot这一层的单词便利完成后dog还是得从字典中删除。即等到当前层所有单词遍历完后，和他们相邻且在字典中的单词要从字典中删除。 如果像上面那样没有立马删除相邻单词，就有可能把同一个单词加入bfs队列中，这样就会有很多的重复计算（比如上面例子提到的dog就会被2次加入队列）。因此我们用一个哈希表来保证加入队列中的单词不会重复，哈希表在每一层遍历完清空（代码中hashtable）。 当某一层的某个单词转换可以得到end单词时，表示已经找到一条最短路径，那么该单词的其他转换就可以跳过。并且遍历完这一层以后就可以跳出循环，因为再往下遍历，肯定会超过最短路径长度

这里我用的是类似level order traversal 的方法

第二个问题：

为了输出最短路径，我们就要在比bfs的过程中保存好前驱节点，比如单词hog通过一次变换可以得到hot，那么hot的前驱节点就包含hog，每个单词的前驱节点有可能不止一个，那么每个单词就需要一个数组来保存前驱节点。为了快速查找因此我们使用哈希表来保存所有单词的前驱路径，哈希表的key是单词，value是单词数组.
有了上面的前驱路径，可以从目标单词开始递归的构造所有最短路径

python dict

Solution

我的code,正确性是对的，但是超时

# -*- coding: utf-8 -*-
from collections import deque
from sets import Set
import sys

class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return a list of lists of string
    def findLadders(self, start, end, dict):
        if not start or not end or not dict:      
            return None
        self.minLength = sys.maxint
        self.resultList = []
        prevHash = {}
        #bfs
        level = 1
        queue = deque()
        removeQueue = Set()
        preEnd = Set()
        queue.append([start, level])
        curLevelNum = 1
        nextLevelNum = 0
        prevHash[start] = None
        while queue:
            c = queue.popleft()
            curr = c[0]
            curLev= c[1]
            curLevelNum -= 1
            removeQueue.add(curr)
            if self.isNeighbour(end, curr):
                preEnd.add(curr)

                #return curLev + 1
            #loop a - z to find neighbors
            ns = self.getNeighbours(curr, dict)
            for word in ns:
                if curr != word:
                    queue.append([word, curLev + 1])
                    removeQueue.add(word)
                    nextLevelNum += 1
                    if word in prevHash:
                        if curr not in prevHash[word]:
                            prevHash[word].append(curr)             
                    else:
                        prevHash[word] = [curr]
            #remove already used word, cause we only need one shortest way here
            if curLevelNum == 0:
                while removeQueue:
                    c = removeQueue.pop()
                    if c in dict:
                        dict.remove(c)
                curLevelNum = nextLevelNum
                nextLevelNum = 0
        for curr in preEnd:
            pa = []
            pa.append(end)
            pa.append(curr)
            pathes = self.getPathes(start, curr, prevHash, pa)
        return self.resultList

    def getNeighbours(self, curr, dict):
        #26 characters(a-z)
        neighbours = []
        l = len(curr)
        for i in range(l):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                s = curr[:i] + c + curr[i+1:]
                if s in dict:
                    neighbours.append(s)
        return neighbours

    def isNeighbour(self, curr, word):
        len1 = len(curr)
        len2 = len(word)
        if len1 != len2:
            return False
        else:
            diff = 0
            for i in range(len1):
                if curr[i] != word[i]:
                    diff += 1
                if diff > 1:
                    return False
            return True

    def getPathes(self, start, curr, prevHash, curList):
        if curr == start:                                                 
            if len(curList) < self.minLength:
                self.minLength = len(curList)
                newList = list(curList)
                newList.reverse()
                self.resultList = [newList]
            elif len(curList) == self.minLength:
                newList = list(curList)
                newList.reverse()
                self.resultList.append(newList)
        else:
            parentList = prevHash[curr]
            for parent in parentList:
                curList.append(parent)
                self.getPathes(start, parent, prevHash, curList)
                curList.pop()

可以通过的code

source code

# -*- coding: utf-8 -*-
from collections import deque
from sets import Set

class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return a list of lists of string
    def findLadders(self, start, end, dict):
        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