Word Ladder

December 24, 2023

Problem #

Given two words, find the shortest chain of words you can create by changing only one letter at a time, such that each word in the chain is a valid English word. You can use a dictionary or online database to check word validity.

Solution #

Solving the “Word Ladder” problem in Python typically involves using a breadth-first search (BFS) algorithm to traverse through word transformations.

Here’s the general idea of the solution:

1. Start with the initial word, and at each step, transform it by changing one letter at a time.
2. Each transformed word must be in the given word list (valid English words).
3. Use BFS to ensure the shortest transformation sequence is found.

First, you need a function to find all possible one-letter transformations of a given word that are in the word list:

def get_neighbors(word, word_list):
    neighbors = []
    for i in range(len(word)):
        for j in range(26):
            if chr(ord('a') + j) != word[i]:
                new_word = word[:i] + chr(ord('a') + j) + word[i+1:]
                if new_word in word_list:
                    neighbors.append(new_word)
    return neighbors

Now, the BFS implementation to find the shortest transformation sequence:

from collections import deque

def word_ladder(begin_word, end_word, word_list):
    if end_word not in word_list:
        return []

    word_list = set(word_list)  # Convert list to set for faster lookups
    queue = deque([(begin_word, [begin_word])])

    while queue:
        current_word, path = queue.popleft()
        if current_word == end_word:
            return path

        for neighbor in get_neighbors(current_word, word_list):
            if neighbor not in path:  # Avoid cycles
                new_path = path + [neighbor]
                queue.append((neighbor, new_path))
                word_list.remove(neighbor)  # Remove to avoid re-visiting

    return []  # No path found

# Example usage
word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
begin_word = "hit"
end_word = "cog"
result = word_ladder(begin_word, end_word, word_list)
print(result)

In this code:

• get_neighbors finds all valid one-letter transformations of a given word.
• word_ladder uses BFS to find the shortest path from begin_word to end_word.
• A queue is used to keep track of the current word and the path taken to reach it.
• The algorithm returns the shortest transformation sequence as a list of words.

You can adapt this code to include a check against a real dictionary or word database, replacing the word_list with API calls or a more comprehensive word list. Keep in mind that such checks can significantly impact the performance due to the increased complexity of word validation.