Word Ladder (LeetCode 127): BFS с шаблонами-джокерами на Python

Задача Word Ladder (LeetCode 127) требует найти длину кратчайшей цепочки от одного слова к другому, меняя по одной букве за раз, причём каждое промежуточное слово должно быть в заданном списке. Кратчайший путь с одинаковыми шагами — это поиск в ширину. Приём, который делает решение быстрым, — группировка слов по шаблонам с подстановочными знаками, например h*t, чтобы не сравнивать каждую пару слов.

Задача

Даны beginWord, endWord и список слов. Верните количество слов в кратчайшей последовательности преобразований от beginWord к endWord, считая оба конца. На каждом шаге меняется ровно одна буква, и каждое слово, к которому вы переходите, должно быть в списке. Верните 0, если такой последовательности нет.

Почему поиск в ширину

Представьте каждое слово как узел, а ребро — между двумя словами, различающимися на одну букву. Каждое ребро стоит один шаг, поэтому кратчайшая последовательность — это кратчайший путь в невзвешенном графе, и поиск в ширину находит его при первом достижении конечного слова.

Построение рёбер перебором

Сравнение каждой пары слов на предмет различия в одну букву стоит O(N в квадрате умножить на L) для N слов длины L. При тысячах слов это медленно. Лучше генерировать соседей из шаблонов.

Подход: шаблоны с подстановочными знаками

Заменяйте каждую букву по очереди на *. hot превращается в *ot, h*t и ho*. Два слова являются соседями ровно тогда, когда у них совпадает шаблон. Постройте отображение из шаблона в слова, которые ему соответствуют, и запустите поиск с его помощью.

from collections import deque, defaultdict

def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
    patterns = defaultdict(list)
    for w in words | {begin_word}:
        for i in range(len(w)):
            patterns[w[:i] + "*" + w[i + 1:]].append(w)
    queue = deque([(begin_word, 1)])
    seen = {begin_word}
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            key = word[:i] + "*" + word[i + 1:]
            for nxt in patterns[key]:
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, steps + 1))
            patterns[key] = []
    return 0

Важны две детали. Начальное слово добавляется в отображение шаблонов, даже если его нет в списке, поскольку вы начинаете с него. И после того как слова шаблона посещены, patterns[key] = [] очищает его, чтобы одна и та же группа не сканировалась снова из каждого другого слова с тем же шаблоном. Это сохраняет общую работу линейной по числу шаблонов.

Сложность

Построение шаблонов занимает O(N умножить на L), а построение каждой строки шаблона стоит O(L), итого примерно O(N умножить на L в квадрате). Поиск обращается к каждому слову один раз и к каждой группе шаблонов один раз — та же оценка. Память — O(N умножить на L в квадрате) для отображения шаблонов, так как каждое слово хранится под L ключами длины L.

Как ускорить: двунаправленный поиск

Запустите один поиск от начального слова и один от конечного и всегда расширяйте меньший фронт. Они встречаются посередине, поэтому каждая сторона ищет только половину глубины. Об этом стоит упомянуть, если интервьюер спросит, как ускорить решение, но кода здесь больше, чем ожидает большинство интервью.

Частые ошибки

• Возврат числа изменений вместо числа слов. Последовательность включает beginWord, поэтому в примере получается 5, а не 4.
• Отсутствие проверки, что endWord есть в списке, перед поиском.
• Построение соседей попарным сравнением и превышение лимита времени.
• Позволение поиску повторно посещать слова, что приводит к циклам или замедлению.
• Использование DFS, который находит путь, но не кратчайший.

Краевые случаи для проверки

Как объяснить это на интервью

1. Переформулируйте задачу как граф и объясните, почему поиск в ширину находит кратчайший путь.
2. Скажите, что попарное сравнение слишком медленное, и введите шаблоны с подстановочными знаками.
3. Напишите отображение шаблонов, очередь и множество посещённых.
4. Скажите, что вы считаете слова, а не правки, и покажите первый пример.
5. Назовите сложность и упомяните двунаправленный поиск.

Я протестировал приведённый выше код против обычного попарного поиска в ширину на 20 000 случайных небольших списках слов, а также на двух примерах из таблицы, прежде чем опубликовать. Такая быстрая случайная проверка — хорошая привычка при практике.

Связанная практика

Смотрите нашу шпаргалку по Big O для терминов сложности, список LeetCode Blind 75 для того, что практиковать дальше, и руководство по ассистенту для собеседований по программированию для практики.

Проговаривайте свой подход вслух, пока пишете код. Транскрипт показывает, сформулировали ли вы ключевое наблюдение до написания. Соблюдайте правила работодателя об AI-инструментах на любом живом ассессменте.