Plain bfs solution in Python (~20 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():
                # initialization
                queue = deque()
                distance = {}
                distance[start] = 1
                queue.append(start)
                # loop in bfs order
                while queue:
                    word = queue.popleft()
                    if word == end:
                        return distance[end]
                    # 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
                                queue.append(new_word)
                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.