LeetCode 126 Word Ladder II

LeetCode 126 Word Ladder II Problem

Download Code
import string
class Solution(object):
    # def findLadders(self, beginWord, endWord, wordlist):
    #     """
    #     :type beginWord: str
    #     :type endWord: str
    #     :type wordlist: Set[str]
    #     :rtype: List[List[int]]
    #     """
    #     # https://leetcode.com/discuss/99348/fast-python-solution-using-dbfs-beats-98%25
    #     def construct_paths(begin, end, tree, path, paths):
    #         if begin == end:
    #             paths.append(path)
    #             return
    #         if begin in tree:
    #             for elem in tree[begin]:
    #                 construct_paths(elem, end, tree, path + [elem], paths)
    #
    #     def add_path(tree, word, neigh, is_forw):
    #         if is_forw:
    #             tree[word] = tree.get(word, []) + [neigh]
    #         else:
    #             tree[neigh] = tree.get(neigh, []) + [word]
    #
    #     def bfs_level(this_lev, oth_lev, tree, is_forw, words_set):
    #         if len(this_lev) == 0:
    #             return False
    #         if len(this_lev) > len(oth_lev):
    #             return bfs_level(oth_lev, this_lev, tree, not is_forw, words_set)
    #         for word in (this_lev | oth_lev):
    #             words_set.discard(word)
    #         next_lev = set()
    #         done = False
    #         while len(this_lev):
    #             word = this_lev.pop()
    #             for c in string.ascii_lowercase:
    #                 for index in range(len(word)):
    #                     neigh = word[:index] + c + word[index + 1:]
    #                     if neigh in oth_lev:
    #                         done = True
    #                         add_path(tree, word, neigh, is_forw)
    #                     if not done and neigh in words_set:
    #                         next_lev.add(neigh)
    #                         add_path(tree, word, neigh, is_forw)
    #         return done or bfs_level(next_lev, oth_lev, tree, is_forw, words_set)
    #
    #     tree, path, paths = {}, [beginWord], []
    #     is_found = bfs_level(set([beginWord]), set([endWord]), tree, True, wordlist)
    #     construct_paths(beginWord, endWord, tree, path, paths)
    #     return paths


    def findLadders(self, beginWord, endWord, wordlist):
        # do not use single dfs or bfs, because both of them
        # try to get result in single direction, which check lots
        # of unnecessary branches
        # https://leetcode.com/discuss/67716/my-30ms-bidirectional-bfs-and-dfs-based-java-solution
        wordlist.discard(beginWord)
        wordlist.discard(endWord)
        hash_map, res = {}, []
        self.bfs(set([beginWord]), set([endWord]), wordlist, False, hash_map)
        print hash_map
        self.dfs(res, [beginWord], beginWord, endWord, hash_map)
        return res

    def bfs(self, forward, backward, wordlist, reverse, hash_map):
        if len(forward) == 0 or len(backward) == 0:
            return
        if len(forward) > len(backward):
            self.bfs(backward, forward, wordlist, not reverse, hash_map)
            return
        is_connected = False
        next_level = set()
        for word in forward:
            for c in string.ascii_lowercase:
                for index in range(len(word)):
                    neigh = word[:index] + c + word[index + 1:]
                    if not reverse:
                        key, value = word, neigh
                    else:
                        key, value = neigh, word
                    if neigh in backward:
                        hash_map[key] = hash_map.get(key, []) + [value]
                        is_connected = True
                    if not is_connected and neigh in wordlist:
                        next_level.add(neigh)
                        hash_map[key] = hash_map.get(key, []) + [value]
                        wordlist.discard(neigh)

        if not is_connected:
            self.bfs(next_level, backward, wordlist, reverse, hash_map)

    def dfs(self, res, path, begin, end, hash_map):
        if begin == end:
            res.append(path)
            return
        try:
            next_step = hash_map[begin]
            for word in next_step:
                self.dfs(res, path + [word], word, end, hash_map)
        except KeyError:
            pass


if __name__ == "__main__":
    s = Solution()
    # print s.findLadders('hit', 'cog', set(["hot","dot","dog","lot","log"]))
    # print s.findLadders('a', 'b', set(['a', 'b', 'c']))
    # print s.findLadders('hot', 'dog', set(['hot', 'dog']))
    # print s.findLadders("qa", "sq", set(["si","go","se","cm","so","ph","mt","db","mb","sb","kr","ln","tm","le","av","sm","ar","ci","ca","br","ti","ba","to","ra","fa","yo","ow","sn","ya","cr","po","fe","ho","ma","re","or","rn","au","ur","rh","sr","tc","lt","lo","as","fr","nb","yb","if","pb","ge","th","pm","rb","sh","co","ga","li","ha","hz","no","bi","di","hi","qa","pi","os","uh","wm","an","me","mo","na","la","st","er","sc","ne","mn","mi","am","ex","pt","io","be","fm","ta","tb","ni","mr","pa","he","lr","sq","ye"]))
    print s.findLadders("hot", "dog", set(["hot","cog","dog","tot","hog","hop","pot","dot"]))

Download Word Ladder II.py

List of all Word Ladder II problems

Leetcode 126 Word Ladder II problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

Feedback is the most important part of any website.

If you have any query, suggestion or feedback, Please feel free to contact us.