126. Word Ladder II

Problem Link

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
        self.adj = adj

    def expand(self):
        last_layer = self.layer[-1]
        new_layer = []
        ret = False
        for i, (u, x) in enumerate(last_layer):
            for v in self.adj[u]:
                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):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :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:
                            self.adj[dictionary[word]].append(dictionary[new_word])
                        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 []