WordLadder.py

from collections import defaultdict

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

# Only one letter can be changed at a time
# Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
# For example,

# Given:
# beginWord = "hit"
# endWord = "cog"
# wordList = ["hot","dot","dog","lot","log","cog"]
# Return
#   [
#     ["hit","hot","dot","dog","cog"],
#     ["hit","hot","lot","log","cog"]
#   ]
# 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.


class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        wordSet = set(wordList)
        charByPos = defaultdict(set)

        for w in wordList:
            for i, ch in enumerate(w):
                charByPos[i].add(ch)
        for w in wordList:
            for i, ch in enumerate(w):
                charByPos[i].add(ch)

        def available_mutations(word):
            ret = []
            for i, c in enumerate(word):
                for ch in charByPos[i]:
                    if ch == c:
                        continue
                    new_word = word[:i] + ch + word[i + 1:]
                    if new_word in wordSet:
                        ret.append(new_word)
            return ret

        stack = [(beginWord, 0)]
        pathes = defaultdict(list)
        shortest = len(wordList) if len(wordList) < 10 else 10
        solutions = []
        visited = set()
        while stack:
            w, idx = stack.pop()
            pathes[idx].append(w)
            if len(pathes[idx]) > shortest:
                continue
            if w == endWord:
                solutions.append(pathes[idx][:])
                shortest = min(shortest, len(pathes[idx]))
                continue
            mutations = available_mutations(w)
            if len(mutations) < 2:
                visited.add(w)
            for i, m in enumerate(mutations):
                if m in visited:
                    continue
                pathes[idx + i] = pathes[idx][:]
                stack.append((m, idx + i))
        return [p for p in solutions if len(p) == shortest]


ex = Solution().findLadders("hit", "cog",
                            ["hot", "dot", "dog", "lot", "log", "cog"])

assert sorted(ex) == [["hit", "hot", "dot", "dog", "cog"],
                      ["hit", "hot", "lot", "log", "cog"]], ex

ex = Solution().findLadders(
    "red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"])

assert sorted(ex) == [['red', 'rex', 'tex',
                       'tax'], ['red', 'ted', 'tex', 'tax'],
                      ['red', 'ted', 'tad', 'tax']], ex