## Tutorial

Use two way BFS. Careful with the graph building process. Enumerate the variations of each word, and check whether the variation is in the dictionary or not. Do not use $O(n^2)$ to try each pair of words, which would cause TLE.

## Solution

class Tree:
def __init__(self, word_list, start_word, mark, vis, adj):
self.word_list = word_list
self.start_word = start_word
index = word_list.index(start_word)
self.layer = [[(index, -1)]]
self.vis = vis
self.vis[index] = mark
self.mark = mark
self.finish = False

def expand(self):
last_layer = self.layer[-1]
new_layer = []
ret = False
for i, (u, x) in enumerate(last_layer):
if self.vis[v] != self.mark:
new_layer.append((v, i))
if self.vis[v] != 0:
ret = True
if not new_layer:
self.finish = True
for v, father in new_layer:
self.vis[v] = self.mark
self.layer.append(new_layer)
return ret

def find(self, index, a):
ret = []
for i in reversed(range(index)):
ret.append(self.word_list[self.layer[i][a][0]]);
a = self.layer[i][a][1];
return ret

def connect(a, b):
if len(a) != len(b):
return False
cnt = 0
for i in range(len(a)):
if a[i] != b[i]:
cnt += 1
return cnt == 1

def construct(a, b):
ret = []
for (u, fu) in a.layer[-1]:
for (v, fv) in b.layer[-1]:
if u == v:
a_list = a.find(len(a.layer) - 1, fu)
b_list = b.find(len(b.layer) - 1, fv)
a_list.reverse()
a_list.append(a.word_list[u])
ret.append(a_list + b_list)
return ret

class Solution(object):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
wordList = list(set(wordList))
if endWord not in wordList:
return []
if endWord == beginWord:
return [[endWord]]
if connect(beginWord, endWord):
return [[beginWord, endWord]]
if beginWord not in wordList:
wordList.append(beginWord)

dictionary = {}
for i, word in enumerate(wordList):
dictionary[word] = i
self.total_len = len(wordList)
self.adj = [[] for i in range(self.total_len)]
for word in wordList:
temp = list(word)
for i in range(len(temp)):
for j in 'abcdefghijklmnopqrstuvwxyz':
if temp[i] != j:
x = temp[i]
temp[i] = j
new_word = ''.join(temp)
if new_word in dictionary:
temp[i] = x

vis = [0] * len(wordList)
tree_top = Tree(wordList, beginWord, 1, vis, self.adj)
tree_bottom = Tree(wordList, endWord, 2, vis, self.adj)

while True:
if tree_top.expand():
return construct(tree_top, tree_bottom)
if tree_bottom.expand():
return construct(tree_top, tree_bottom)
if tree_top.finish and tree_bottom.finish:
return []
return []