Assume the size of set is N. If we consider the worse case: the two sets meet as we visit the very last string. Given that two sets are balanced, each set contains N/2 strings in the worst case. If each word branches out M new words, the height of the 'tree' in 'two-end BFS' should be O(log(N/2)/log(M)), compared to O(log(N)/log(M)) in 'one-end BFS'.
The fact is, the number of branches generated by words decays as the search becomes deeper, because some branches are already visited.
I don't think this is an instance of Dijkstra's algorithm and there is no reason to use Dijkstra's algorithm in this problem. In fact using Dijkstra's algorithm in this case where all edge weights are the same will have a worse performance O((V+E)*logV) compared to BFS's O(V+E).
def ladderLength(self, beginWord, endWord, wordDict):
if endWord not in wordDict:
length = 2
front, back = set([beginWord]), set([endWord])
wordDict = set(wordDict)
# generate all valid transformations
front = wordDict & (set(word[:index] + ch + word[index+1:] for word in front
for index in range(len(beginWord)) for ch in string.ascii_lowercase))
if front & back:
# there are common elements in front and back, done
length += 1
if len(front) > len(back):
# swap front and back for better performance (fewer choices in generating nextSet)
front, back = back, front
# remove transformations from wordDict to avoid cycle
wordDict -= front
Seems like we need to check if the endWord exists in the dictionary before we call the helper, or it won't pass the test case where the endWord does not exist in the dictionary but some words with 1 distance to the endWord exists in the dictionary.
If using DFS to compute the shortest path, the order of visiting nodes should first be topologically sorted. If it is not, there may be loops in the DFS forest (recursive tree). For BFS, the visiting order is naturally topologically sorted.