## LeetCode 126 Word Ladder II Problem

``````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):
#         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
#                     if not done and neigh in words_set:
#         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

# 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
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:
hash_map[key] = hash_map.get(key, []) + [value]

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('a', 'b', set(['a', 'b', 'c']))
# print s.findLadders('hot', 'dog', set(['hot', 'dog']))