[LeetCode] 127. Word Ladder

Problem : https://leetcode.com/problems/word-ladder/

Consider every word in wordList is a node of a graph. Use BFS to find the shortest path from begin word to end word.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        INT_MAX = 2 ** 31 - 1
        N = len(beginWord)
        
        wordDict = {word: INT_MAX for word in wordList}
        intermediates = defaultdict(list)
        
        if endWord not in wordDict: return 0
        
        for word in wordList:
            for i in range(N):
                wordMask = word[:i] + '*' + word[i+1:]
                intermediates[wordMask].append(word)
        
        queue = deque([beginWord])
        step = 1
        
        while queue:
            for _ in range(len(queue)):
                word = queue.popleft()
                
                for i in range(N):
                    wordMask = word[:i] + '*' + word[i+1:]

                    for newWord in intermediates[wordMask]:
                        if newWord == endWord:
                            return step + 1
                        
                        if newWord == word or wordDict[newWord] < step + 1:
                            continue
                        
                        wordDict[newWord] = step + 1
                        queue.append(newWord)

            step += 1
        
        return 0

Bidirectional BFS

Time complexity = O ( N * W * N + N * W * N ) = O ( W * N ** 2), N = length of each word, W = total number of word.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        INT_MAX = 2 ** 31 - 1
        N = len(beginWord)
        
        wordDict = {word: INT_MAX for word in wordList}
        intermediates = defaultdict(list)
        
        if endWord not in wordDict: return 0
        
        for word in wordList:
            for i in range(N):
                wordMask = word[:i] + '*' + word[i+1:]
                intermediates[wordMask].append(word)
        
        queue = set([beginWord])
        opposite = set([endWord])
        
        step = 1
        
        while queue:
            tmp = []
            
            for word in queue:
                for i in range(N):
                    wordMask = word[:i] + '*' + word[i+1:]

                    for newWord in intermediates[wordMask]:
                        if newWord in opposite:
                            return step + 1
                        
                        if newWord == word or wordDict[newWord] < step + 1:
                            # word has been visited
                            continue
                        
                        wordDict[newWord] = step + 1
                        tmp.append(newWord)
                        
            queue = set(tmp) if len(tmp) < len(opposite) else opposite
            opposite = opposite if len(tmp) < len(opposite) else set(tmp)
            
            step += 1
        
        return 0