class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return a list of lists of string
    def findLadders(self, start, end, dict):
        dict.add(start); dict.add(end)
        curLevel, nextLevel = set(), set()
        curLevel.add(start)
        prevWords, res = {}, []

        while curLevel:
            for curWord in curLevel:
                dict.remove(curWord)
            for curWord in curLevel:
                for i in xrange(len(curWord)):
                    left, right = curWord[:i], curWord[i + 1:]
                    for offset in xrange(1, 26):
                        mid = chr((ord(curWord[i]) - ord('a') + offset) % 26 + ord('a'))
                        newWord = left + mid + right
                        if newWord in dict:
                            nextLevel.add(newWord)
                            if newWord not in prevWords:
                                prevWords[newWord] = set()
                            prevWords[newWord].add(curWord)
            if end in prevWords:
                self.constructPathes(prevWords, start, end, [end], res)
                break
            curLevel = nextLevel
            nextLevel = set()
        return res

    def constructPathes(self, prevWords, start, end, l, res):
        if end == start:
            res.append(l)
            return

        s = prevWords[end]
        for word in s:
            self.constructPathes(prevWords, start, word, [word] + l, res)