python, bidirectional bfs, pre-compute


  • 0
    S
    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            import collections
            wordList.append(beginWord)
            if endWord not in wordList:
                return 0
            dic = {}
            for word in wordList:
                for i in range(len(word)):
                    temp = word[:i] + "_" + word[i+1:]
                    if temp not in dic:
                        dic[temp] = set([word])
                    else:
                        dic[temp].add(word)
            que1 = collections.deque()
            que1.append((beginWord,1))
            que2 = collections.deque()
            que2.append((endWord,1))
            visited1 = {beginWord:1}
            visited2 = {endWord:1}
            while que1 and que2:
                if len(que2) < len(que1):
                    que1,visited1, que2,visited2 = que2,visited2,que1,visited1
                (word,depth) = que1.popleft()
                for i in range(len(word)):
                    newword = word[:i] + "_" + word[i+1:]
                    if newword in dic:
                        for nextword in dic[newword]:
                            if nextword in visited2:
                                return depth + visited2[nextword]
                            if nextword not in visited1:
                                visited1[nextword] = depth + 1
                                que1.append((nextword,depth + 1))
            return 0
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.