Solution by jingjing5


  • 0
    J

    Approach #1 One-direction BFS + Queue [Time Limit Exceeded]

    Intuition

    Start from the begin word, change one character, put it into the path if it exists in the dictionary.

    Algorithm

    Use a queue to record all the paths we have passed from the begin word. When reach the end word, put the path to the results.

    Python

    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: List[List[str]]
            """
            words = set(wordList)
            if endWord not in words or len(beginWord) != len(endWord):
                return []
            forward = collections.deque()
            forward.append([beginWord])
            res = []
            while len(forward):
                size = len(forward)
                for i in range(size):
                    path = forward.popleft()
                    word = path[-1]
                    for k in range(len(word)):
                        for char in 'qwertyuiopasdfghjklzxcvbnm':
                            new_word = word[:k] + char + word[k+1:]
                            if new_word != word:
                                new_path = path + [new_word]
                                if new_word == endWord:
                                    res.append(new_path)
                                if new_word in words:
                                    forward.append(new_path)
                if len(res) > 0:
                    break
            return res
    

    Complexity Analysis

    • Time complexity : $$O(n * 26 ^ l)$$, where n is the number of words in the dictionary, l is the length of the word.

    • Space complexity : $$O(n + m * k * l)$$. We need $$O(n)$$ space to convert the wordList to a dictionary. m is the number of paths, k is the length of each path.


    Approach #2 Bi-direction BFS + Queue [Time Limit Exceeded]

    Algorithm

    Start from both begin word and end word, choose the direction with less paths in each iteration. Pay attention to that when we go backward, the path should be reversed.

    Python

    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: List[List[str]]
            """
            words = set(wordList)
            if endWord not in words or len(beginWord) != len(endWord):
                return []
            forward = collections.deque()
            backward = collections.deque()
            forward.append([beginWord])
            backward.append([endWord])
            res = []
            reverse = False
            while len(forward) and len(backward):
                if len(forward) > len(backward):
                    tmp = forward
                    forward = backward
                    backward = tmp
                    if reverse == False:
                        reverse = True
                    else:
                        reverse = False
                size = len(forward)
                for i in range(size):
                    path = forward.popleft()
                    word = path[-1]
                    for k in range(len(word)):
                        for char in 'qwertyuiopasdfghjklzxcvbnm':
                            new_word = word[:k] + char + word[k+1:]
                            if new_word != word:
                                new_path = path + [new_word]
                                for another_path in backward:
                                    if new_word == another_path[-1]:
                                        tmp = path + another_path[::-1]
                                        if reverse == True:
                                            tmp = tmp[::-1]
                                        res.append(tmp)
                                if new_word in words:
                                    forward.append(new_path)
                if len(res) > 0:
                    break
            return res
    

    Complexity Analysis

    • Time complexity : $$O(n * 26 ^ l)$$, where n is the number of words in the dictionary, l is the length of the word.

    • Space complexity : $$O(n + m * k * l)$$. We need $$O(n)$$ space to convert the wordList to a dictionary. m is the number of paths, k is the length of each path.


    Approach #3 One-direction BFS + DFS + Queue [Accepted]

    Algorithm

    Use BFS to build the graph, then use DFS to find the paths. We can record the parents for each word or the children for each word, depending on which direction to go. Here I prefer recoding the parents as search from end word to begin word can reduce the search space, which reduced both time and space. Even though the time complexity and space complexity look like the same like previous solution, in fact, the code become much faster as the m (the number of paths to search) become much smaller.

    Python

    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: List[List[str]]
            """
            words = set(wordList)
            if endWord not in words or len(beginWord) != len(endWord):
                return []
            words.remove(endWord)
            if beginWord in words:
                words.remove(beginWord)
            forward = collections.deque()
            forward.append(beginWord)
            steps = {}
            steps[beginWord] = 1
            parents = collections.defaultdict(list)
            res = []
            found = False
            step = 0
            while len(forward):
                step += 1
                size = len(forward)
                for i in range(size):
                    word = forward.popleft()
                    for k in range(len(word)):
                        for char in 'qwertyuiopasdfghjklzxcvbnm':
                            if char == word[k]:
                                continue
                            new_word = word[:k] + char + word[k+1:]
                            if new_word == endWord:
                                parents[new_word].append(word)
                                found = True
                            else:
                                if new_word in steps and step < steps[new_word]:
                                    parents[new_word].append(word)
                            if new_word in words:
                                words.remove(new_word)
                                forward.append(new_word)
                                steps[new_word] = steps[word] + 1
                                parents[new_word].append(word)
                if found:
                    break
            if found:
                cur = [endWord]
                self.dfs(endWord, beginWord, parents, cur, res)
            return res
        def dfs(self, curWord, beginWord, parents, cur, res):
            if curWord == beginWord:
                res.append(cur[::-1])
                return
            for parent in parents[curWord]:
                cur.append(parent)
                self.dfs(parent, beginWord, parents, cur, res)
                cur.pop()
    

    Complexity Analysis

    • Time complexity : $$O(n * 26 ^ l)$$, where n is the number of words in the dictionary, l is the length of the word.

    • Space complexity : $$O(2 * n + m * k * l)$$. We need $$O(n)$$ space to convert the wordList to a dictionary and $$O(n)$$ space to build up the graph. m is the number of paths, k is the length of each path.


    Approach #4 One-direction BFS + DFS + Hashset [Accepted]

    Algorithm

    Use set to optimize the Solution 3.

    Python

    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: List[List[str]]
            """
            words = set(wordList)
            if endWord not in words or len(beginWord) != len(endWord):
                return []
            words.remove(endWord)
            if beginWord in words:
                words.remove(beginWord)
            forward = set()
            forward.add(beginWord)
            parents = collections.defaultdict(list)
            res = []
            found = False
            while len(forward) and not found:
                tmp = set()
                for word in forward:
                    for k in range(len(word)):
                        for char in 'qwertyuiopasdfghjklzxcvbnm':
                            if char == word[k]:
                                continue
                            new_word = word[:k] + char + word[k+1:]
                            if new_word == endWord:
                                parents[new_word].append(word)
                                found = True
                            if new_word in words:
                                tmp.add(new_word)
                                parents[new_word].append(word)
                forward = tmp
                for word in tmp:
                    words.remove(word)
            if found:
                cur = [endWord]
                self.dfs(endWord, beginWord, parents, cur, res)
            return res
        def dfs(self, curWord, beginWord, parents, cur, res):
            if curWord == beginWord:
                res.append(cur[::-1])
                return
            for parent in parents[curWord]:
                cur.append(parent)
                self.dfs(parent, beginWord, parents, cur, res)
                cur.pop()
    

    Complexity Analysis

    • Time complexity : $$O(n * 26 ^ l)$$, where n is the number of words in the dictionary, l is the length of the word.

    • Space complexity : $$O(2 * n + m * k * l)$$. We need $$O(n)$$ space to convert the wordList to a dictionary and $$O(n)$$ space to build up the graph. m is the number of paths, k is the length of each path.


    Approach #5 Bi-direction BFS + DFS + Hashset [Accepted]

    Algorithm

    Go bi-direction to build the graph.

    Python

    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: List[List[str]]
            """
            words = set(wordList)
            if endWord not in words or len(beginWord) != len(endWord):
                return []
            words.remove(endWord)
            if beginWord in words:
                words.remove(beginWord)
            forward = set()
            forward.add(beginWord)
            backward = set()
            backward.add(endWord)
            parents = collections.defaultdict(list)
            res = []
            found = False
            reverse = False
            while len(forward) and not found:
                if len(forward) > len(backward):
                    tmp = forward
                    forward = backward
                    backward = tmp
                    reverse = not reverse
                tmp = set()
                for word in forward:
                    for k in range(len(word)):
                        for char in 'qwertyuiopasdfghjklzxcvbnm':
                            if char == word[k]:
                                continue
                            new_word = word[:k] + char + word[k+1:]
                            if new_word in backward:
                                if reverse:
                                    parents[word].append(new_word)
                                else:
                                    parents[new_word].append(word)
                                found = True
                            if new_word in words:
                                tmp.add(new_word)
                                if reverse:
                                    parents[word].append(new_word)
                                else:
                                    parents[new_word].append(word)
                forward = tmp
                for word in tmp:
                    words.remove(word)
            if found:
                cur = [endWord]
                self.dfs(endWord, beginWord, parents, cur, res)
            return res
        def dfs(self, curWord, beginWord, parents, cur, res):
            if curWord == beginWord:
                res.append(cur[::-1])
                return
            for parent in parents[curWord]:
                cur.append(parent)
                self.dfs(parent, beginWord, parents, cur, res)
                cur.pop()
    

    Complexity Analysis

    • Time complexity : $$O(n * 26 ^ l)$$, where n is the number of words in the dictionary, l is the length of the word.

    • Space complexity : $$O(2 * n + m * k * l)$$. We need $$O(n)$$ space to convert the wordList to a dictionary and $$O(n)$$ space to build up the graph. m is the number of paths, k is the length of each path.


Log in to reply
 

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