Word Ladder

Treat the dictionary as a graph where two words are connected if they differ in exactly one position, and find the shortest path from the start word to the end word with breadth first search. Instead of comparing every pair of words, you generate the neighbours of the current word by trying every position and every replacement letter, and check each generated candidate against the set of allowed words.

The trick that makes it fast is removing words from the dictionary as you visit them. Since the search only ever needs to reach each word once, a word that has already been used does not need to be considered again, and deleting it also stops other branches from re-expanding it.

The mechanism is that BFS explores in order of the number of steps taken, so the first time you reach the end word you have arrived by the shortest ladder. The set of remaining words acts as the visited structure, since a word that is no longer in the set has already been reached.

The trade-off to name is the cost of generating neighbours. There are n positions and twenty six candidate letters, so each expansion produces twenty six n candidate strings, and building those strings is not free. The alternative is a bidirectional search, which expands from both ends and roughly squares the search space, which is a substantial win on long ladders. The other detail is that the start word must be in the dictionary or handled separately, since it may or may not be reachable.

Generate the one letter neighbours of the current word and use breadth first search over the words that are still allowed.

from collections import deque


def word_ladder(begin, end, words):
    remaining = set(words)
    if end not in remaining:
        return 0
    queue = deque([(begin, 1)])
    while queue:
        word, steps = queue.popleft()
        if word == end:
            return steps
        for i in range(len(word)):
            for letter in "abcdefghijklmnopqrstuvwxyz":
                if letter == word[i]:
                    continue
                candidate = word[:i] + letter + word[i + 1:]
                if candidate in remaining:
                    remaining.remove(candidate)
                    queue.append((candidate, steps + 1))
    return 0


words = ["hot", "dot", "dog", "lot", "log", "cog"]
print(word_ladder("hit", "cog", words))
print(word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))

The outputs are 5 and 0. The first ladder is hit to hot to dot to dog to cog, which is five words and therefore four changes, and the answer counts the words. The second call fails because the end word is not in the dictionary at all.

The mechanism is that removing a word from the set when it is enqueued marks it as visited, so it can never be enqueued twice and the search cannot loop. The step counter starts at one for the begin word, so the result counts words rather than changes, which is the convention most versions of this problem use.

The trade-off to name is the letter loop. For every word the function tries twenty six replacements in each position, so the work is proportional to the length of the word times twenty six, times the number of words expanded. If the words are long, generating candidates with string slicing is the expensive part, and a more efficient implementation reuses the prefix and suffix around the changed position. The other detail is the early exit when the end word is missing, which avoids a pointless full search.