Python iterative solution based on LC127. Use dict to store neighbours.

  • 1

    Just an upgrade of LC127 using a list to store the paths.
    Based on LC127.

    To get rid of TLE, just delete the visited keys after searching them.

    class Solution(object):
        def findLadders(self, beginWord, endWord, wordlist):
            :type beginWord: str
            :type endWord: str
            :type wordlist: Set[str]
            :rtype: List[List[int]]
            # add endWord into list
            # create a map of neighbours to wordList:
            d = {}
            for word in wordlist:
                for i in range(len(word)):
                    key = word[:i] + '_' + word[i + 1:]
                    d[key] = d.get(key, []) + [word]
            # find neighbours and check if match
            cur = [[beginWord]]
            res = []
            while not res:
                if not cur:
                new = []
                keys=[] # delete keys after searching
                for words in cur:
                    word = words[-1]
                    for i in range(len(word)):
                        key = word[:i] + '_' + word[i + 1:]
                        if key in d:
                            for target in d[key]:
                                if word != target:
                                    new.append(words + [target])
                                    if target == endWord:
                                        res.append(words + [target])
                for key in keys:
                    d.pop(key, None)
                cur = new
            return res

  • 0

    @szhu3210 I think to add the line wordlist.add(endWord) results in duplicate lists in the final result. Otherwise clear and readable.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.