BFS python 752ms


  • 0
    Z
    from collections import deque
    letters = list('abcdefghijklmnopqrstuvwxyz')
    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            def findAllNeighbors(word_dist, wordList, queue, explored):
                for i in range(len(word_dist[0])):
                    for l in letters:
                        neighbor = word_dist[0][:i]+ l + word_dist[0][i+1:]
                        if neighbor != word_dist[0] and neighbor in wordList and neighbor not in explored:
                            queue.append((neighbor, word_dist[1]+1))
                            explored.add(neighbor)
            word_set = set(wordList)
            queue = deque()
            queue.append((beginWord,1))
            explored = set()
            while(len(queue)>0):
                word_dist = queue.popleft()
                if word_dist[0] == endWord:
                    return word_dist[1]
                findAllNeighbors(word_dist, word_set, queue, explored)
            return 0

Log in to reply
 

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