https://leetcode.com/problems/word-ladder-ii/description/#

word-ladder-ii.py

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        connection = {w: set() for w in wordList}
        
        def is_similar(w1, w2):
            diff_c = False
            for i,c in enumerate(w1):
                if c != w2[i]:
                    if diff_c: return False
                    diff_c = True
            return True

        wordList.append(beginWord)
        for word1 in wordList:
            for word2 in wordList:
                if word1 != word2 and is_similar(word1, word2):
                    connection.setdefault(word1, set()).add(word2)
                    connection.setdefault(word2, set()).add(word1)
                    
        # print connection
        
        to_check = [[beginWord]]
        seen_words = set([beginWord])
        results = []
        min_dist = len(wordList) + 1
        while to_check:
            # print to_check
            path = to_check.pop(0)
            if len(path) > min_dist: continue
            if path[-1] == endWord:
                if len(path) < min_dist: min_dist = len(path)
                results.append(path)
            seen_words.add(path[-1])
            to_check.extend(path + [w] for w in connection[path[-1]] if w not in seen_words)
        return results