[LeetCode] 126. Word Ladder II

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

Consider every word in the wordList is a node of a graph. 

On each node, we may replace the letters of the word to find the next words.

The problem equals find the shortest routines from the begin word to the end word in this graph.

The solution includes two steps.  Firstly, use BFS approach to find the shortest routines from begin word to end word. Meanwhile, save the parent of each visited word. Word A is parent of word B if A can transform to B by replacing a letter.  Secondly, reconstruct routines from end word back to begin word by using the saved parent info of words on shortest routines.

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        # impossible to transform if endWord is not in wordList.
        if endWord not in wordList: return []
        
        # construct word mask map
        wordMap = defaultdict(list)
        
        for word in wordList:
            for i in range(len(word)):
                mask = word[:i] + "#" + word[i+1:]
                wordMap[mask].append(word) 
        
        # save the previous word was used to transform to current word
        preWord = defaultdict(list)
        
        # save the minimum step to transform to current word
        visited = defaultdict(lambda : 2 ** 31 - 1)
        visited[beginWord] = 0
        
        # use bfs to find all possible transformation paths
        step = 1
        queue = deque([beginWord])
        
        while queue:
            found = False
            
            for _ in range(len(queue)):
                word = queue.popleft()

                if word == endWord:
                    found = True

                for i in range(len(word)):
                    mask = word[:i] + "#" + word[i+1:]
                    for nxtWord in wordMap[mask]:
                        if nxtWord == word:
                            # skip the current word
                            continue

                        if visited[nxtWord] < step:
                            # already find the shortest path to nxtWord
                            continue
                        
                        if visited[nxtWord] != step:
                            # find the shortest path to nxtWord
                            visited[nxtWord] = step
                            # add nxtWord to queue if this is the first time we reach to it
                            queue.append(nxtWord)
                        
                        # save the previous word of nxtWord
                        preWord[nxtWord].append(word)
            
            step += 1
            if found:
                break
            
        # there is no way to reach to endWord
        if not preWord[endWord]:
            return []
        
        # use dfs to construct the transformation path
        result = []
        stack = []
        stack.append((endWord, [endWord]))
        
        while stack:
            word, tmp = stack.pop()
            
            if word == beginWord:
                result.append(tmp[::-1])
            else:
                for pre in preWord[word]:
                    stack.append((pre, tmp + [pre]))
        
        return result

Edited on 06/19/2021. Optimize performance.

Edited on 07/24/2021. Optimize performance.