Fast and elegant two-end bfs solution in Python (~30 lines)


  • 0
    I
    from collections import deque
    
    class Solution(object):
        def ladderLength(self, start, end, word_list):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: int
            """
            def bfs():
                # corner case
                if end not in words:
                    return 0
                # initialization
                forth, back = deque(), deque()
                dforth, dback = {}, {} 
                dforth[start] = 1
                dback[end] = 1
                forth.append(start)
                back.append(end)
                turn = True # if true it's forth turn, else back's
                # loop in bfs order
                while forth and back:
                    frontier = (forth if turn else back) or forth or back # frontier is not empty that way
                    distance = (dforth if turn else dback) or dforth or dback
                    word = frontier.popleft()
                    # found intersection
                    if ((frontier is forth and word in dback) or (frontier is back and word in dforth)):
                        return dforth[word] + dback[word] - 1 # word was counted twice
                    # for every position in the word, try all possible changes in character
                    for i in range(word_length):
                        for ch in 'abcdefghijklmnopqrstuvxwyz':
                            new_word = word[:i] + ch + word[i + 1:]
                            # new_word not visited and in the word dictionary
                            if new_word in words and new_word not in distance:
                                distance[new_word] = distance[word] + 1
                                frontier.append(new_word)
                    turn = not turn
                return 0
            word_length = len(start)
            words = set(word_list)
            return bfs()
    

Log in to reply
 

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