# Solution by jingjing5

• #### 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):
"""
: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):
"""
: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):
"""
: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):
"""
: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()
parents = collections.defaultdict(list)
res = []
found = False
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:
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):
"""
: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()
backward = set()
parents = collections.defaultdict(list)
res = []
found = False
reverse = False
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:
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.

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