from collections import defaultdict, namedtuple
from heapq import heappush, heappop
class NotFound(Exception):
pass
def word_ladder(words, start, end):
"""Return a word ladder (a list of words each of which differs from
the last by one letter) linking start and end, using the given
collection of words. Raise NotFound if there is no ladder.
>>> words = 'card care cold cord core ward warm'.split()
>>> ' '.join(word_ladder(words, 'cold', 'warm'))
'cold cord card ward warm'
"""
# Find the neighbourhood of each word.
placeholder = object()
matches = defaultdict(list)
neighbours = defaultdict(list)
for word in words:
for i in range(len(word)):
pattern = tuple(placeholder if i == j else c
for j, c in enumerate(word))
m = matches[pattern]
m.append(word)
neighbours[word].append(m)
# A* algorithm: see https://en.wikipedia.org/wiki/A*_search_algorithm
# Admissible estimate of the steps to get from word to end.
def h_score(word):
return sum(a != b for a, b in zip(word, end))
# Closed set: of words visited in the search.
closed_set = set()
# Open set: search nodes that have been found but not yet
# processed. Accompanied by a min-heap of 4-tuples (f-score,
# g-score, word, previous-node) so that we can efficiently find
# the node with the smallest f-score.
Node = namedtuple('Node', 'f g word previous')
open_set = set([start])
open_heap = [Node(h_score(start), 0, start, None)]
while open_heap:
node = heappop(open_heap)
if node.word == end:
result = []
while node:
result.append(node.word)
node = node.previous
return result[::-1]
open_set.remove(node.word)
closed_set.add(node.word)
g = node.g + 1
for neighbourhood in neighbours[node.word]:
for w in neighbourhood:
if w not in closed_set and w not in open_set:
g = node.g + 1
next_node = Node(h_score(w) + g, g, w, node)
heappush(open_heap, next_node)
open_set.add(w)
raise NotFound("No ladder from {} to {}".format(start, end))
Suppose that there are \$ n \$ words of \$ m \$ letters, and \$ e \$ edges in the graph of words. Then this algorithm takes \$ O(m^2n) \$ to find the edges and then \$ O(e + m^2n + n \log n) \$\$ O(e + mn + n \log n) \$ to find the shortest path.
