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()
    

  • 0
    S

    It's a neat way to track depth of each node, but it doubles space complexity.


Log in to reply
 

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