Problem Link:
http://oj.leetcode.com/problems/word-ladder-ii/
Basically, this problem is same to Word Ladder I, which uses a double-direction BFS. However, the difference is that we need to keep track of all paths during the double-direction BFS in order to output all possible shortest paths from the start word to the end word. To do this, we use the build-in dictionary strucutre in python. After the BFS, we need another normal BFS from the start word following the path dictionary, and return all paths reaching the end word.
Python performance issue. During the constructing the path dictionary, we need to check whether the key already exists. We can use dict.has_key() or key in dict.keys(), however both ways get a TLE by oj.leetcode.com. In this case, we can use dict.setdefault(key, default_value) or try...except... clause to accelerate such operations.
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return an integer
def findLadders(self, start, end, dict):
"""
Similar to solving WordLadder 1, we use a double-direction BFS.
However, instead of only storing the last word of each path (front edges),
we need to store the entire path.
In the code for solving WordLadder 1,
we check two fronts meet during extending the paths,
but this problem asks for all possible shortest path,
so we need to extend all paths and then check all pairs of paths from start and end.
"""
# Special cases
if start == end:
return [start] # The length of words
WORD_LENGTH = len(start) # New words in one step
new_words = set() # Initialize the set of visited words
start_front = set()
start_front.add(start)
start_visited = set()
start_visited.add(start) end_front = set()
end_front.add(end)
end_visited = set()
end_visited.add(end) # Add end to the dictionary
dict.add(end) # Traverse map
next_words = {} meet = False
# Extend the two fronts and check if they can meet
while not meet:
# Extend the start front
new_words.clear()
for w in start_front:
next_words[w] = []
for i in xrange(WORD_LENGTH):
for candidate in [w[:i]+chr(97+c)+w[i+1:] for c in xrange(26)]:
if candidate in dict and candidate not in start_visited:
next_words[w].append(candidate)
new_words.add(candidate)
if new_words:
# Update visited words
start_visited.update(new_words)
start_front = new_words.copy()
else:
return [] # Check if two fronts meet
if start_front & end_front:
break # Extend the end front
new_words.clear()
for w in end_front:
for i in xrange(WORD_LENGTH):
for candidate in [w[:i]+chr(97+c)+w[i+1:] for c in xrange(26)]:
if candidate in dict and candidate not in end_visited:
next_words.setdefault(candidate, []).append(w)
#try:
# next_words[candidate].append(w)
#except:
# next_words[candidate] = [w]
new_words.add(candidate)
if new_words:
end_visited.update(new_words)
end_front = new_words.copy()
else:
return []
# Check if two fronts meet
if start_front & end_front:
break
# BFS from start to end
res = []
path = [[start]]
while res == []:
new_path = []
for p in path:
try:
for w in next_words[p[-1]]:
new_path.append(p+[w])
if w == end:
res.append(p+[w])
except:
pass
path = new_path
# Return all paths in res
return res