Python Solution (BFS with preprocessing)


  • 0
    Y
    import collections
    class Solution(object):
        def preprocess(self, word_list, l):
            dic = {}
            for word in word_list:
                for i in xrange(l):
                    new = word[:i] + "?" + word[i+1:]
                    dic[new] = dic.get(new, []) + [word]
                    
            return dic
            
        def findLadders(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: List[List[str]]
            """
            wordSet = set(wordList)
            if endWord not in wordSet:
                return []
    
            search_que = collections.deque()
            visited = {}
            word_len = len(beginWord)
            visited[beginWord] = 1
            word_dic = self.preprocess([beginWord] + wordList, word_len)
            prev_dic = {}
            break_flag = False
            search_que.append((beginWord, [], 1))
            rst = []
            shortest = None
            while search_que:
                word_tup = search_que.popleft()
                word, path, dist = word_tup
                if shortest and dist > shortest:
                    break
                for ind in xrange(word_len):
                    cur_word = word[:ind] + "?" + word[ind+1:]
                    neighbors = word_dic[cur_word]
                    for neighbor in neighbors:
                        if neighbor == word:
                            continue
                        tup = (neighbor, path + [word], dist + 1)
                        if neighbor == endWord:
                            rst.append(tup[1] + [endWord])
                            shortest = dist
                            continue
                        if neighbor not in visited or visited[neighbor] >= dist:
                            search_que.append(tup)
                            visited[neighbor] = dist
            return rst  
    

Log in to reply
 

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