How do you solve the word ladder problem, where each step changes one letter?
You treat the words as the nodes of a graph and each word as a vertex. Two words are joined if they differ in one letter. Then you use BFS to find the shortest route.
So the first thing is to build the graph, or at least to be able to ask whether two words are joined. There are two ways.
# Compare every pair of words.
def one_letter_apart(first, second):
if len(first) != len(second):
return False
different = 0
for a, b in zip(first, second):
if a != b:
different += 1
if different > 1:
return False
return different == 1
The other way is to write down every word you could make by changing one letter of a given word, and then look those up in a set. That way you only do the work for the words you actually visit.
import string
def neighbours(word, words):
result = []
for i in range(len(word)):
for letter in string.ascii_lowercase:
if letter == word[i]:
continue
candidate = word[:i] + letter + word[i + 1:]
if candidate in words:
result.append(candidate)
return result
And then the BFS is the ordinary one. You start at the first word and you look at the neighbours of each word you reach. The first time you reach the end word is the shortest route, because BFS looks at the routes in order of length.
And the trick that makes it fast is that you remove each word from the set of unused words as soon as you have visited it. Otherwise the same word gets explored again and again through different routes, and the search becomes very slow.
the words the unused set at the start
------------ ----------------------------------------
hit, hot, hat, het all four
after visiting hot the hot is taken out
so hot is only explored once
And the complexity is O of the number of words times the length of a word times the size of the alphabet for the neighbour search, plus the cost of the BFS itself.
So the rule to remember is this. BFS over the words, and take each word out of the set when you visit it.
The last question in this topic shows the code.