Shortest path via BFS on implicit graph of words, induced by the dictionary of words, with an edge between each pair of words that differ by a single character.

words.py

import sys
import collections
import string
import logging


logging.basicConfig(level=logging.DEBUG)
LOGGER = logging.getLogger(__name__)


def shortest_path(beg, end, words, alphabet):
	if beg == end:
		return [beg]

	seen = {w: False for w in words}
	queue = [(beg, [beg])]
	while queue:
		w, l = queue.pop()
		for idx in range(len(w) + 1):
			for oth in alphabet:
				new_s = w[:idx] + oth + w[idx+1:]
				if new_s == end:
					return l+[new_s]
				elif new_s in seen and not seen[new_s]:
					queue.insert(0, (new_s, l+[new_s]))
					seen[new_s] = True

	LOGGER.info("No path from '%s' to '%s' exists in this dictionary", beg, end)

	return []

if __name__ == '__main__':
	beg, end = sys.argv[1:]

	alphabet = set(string.ascii_lowercase)

	words = set()
	with open('wordsEn.txt') as f:
		words = set([w.strip() for w in f])

	alphabet.add('') # so that we can remove characters

	P = shortest_path(beg, end, words, alphabet)
	print(' -> '.join(P))