126. Word Ladder II.md

126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Code

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        def diff_by_one(w1, w2):
            length = len(w1)
            flag = 0
            for i in range(length):
                if w1[i] != w2[i]:
                    if flag == 1:
                        return False
                    flag += 1
            return flag==1
            
        def helper(word):
            stack = []
            paths = []
            stack.append(word)
            paths.append([word])
            notfound = True
            visited = [False for _ in range(len(wordList))]
            
            while stack and notfound:
                stack_len = len(stack)
                while stack_len > 0:
                    stack_len -= 1
                    word = stack.pop(0)
                    path = paths.pop(0)
                    if word == endWord:
                        notfound = False
                        res.append(path[:])
                        
                    for cur in wordList:
                        if cur not in path and diff_by_one(word, cur):
                            path.append(cur)
                            stack.append(cur)
                            paths.append(path[:])
                            path.pop()

            
            
        res = []
        length = len(wordList)
        visited = [False for _ in range(length)]
        if endWord not in wordList:
            return res
        
        helper(beginWord)        
        return res