Word Ladder

Q: Может ли двунаправленный BFS ускорить решение задачи Word Ladder?

Да. Одновременно выполняй поиск от beginWord и от endWord , каждый раз расширяя меньшую сторону на один уровень, и остановись, когда новая вершина уже достигнута с другой стороны. Тогда в цепочке будет на одно слово больше, чем суммарное количество изменений с обеих сторон. Если у каждого слова около b соседей, а для построения цепочки требуется d изменений, один поиск может затронуть около b^d слов, а два поиска, встретившиеся посередине, затронут около 2 × b^(d/2) .

СложноГрафы Очередь

+10

Даны два слова: beginWord и endWord, а также список слов wordList. Лестница — это последовательность слов, которая начинается с beginWord, заканчивается на endWord и в которой каждое следующее слово отличается от предыдущего ровно одной буквой. Все слова после beginWord должны содержаться в wordList.

Верните количество слов в кратчайшей лестнице, включая оба конца, или 0, если лестницы не существует. Например, cold, cord, card — это лестница из 3 слов. beginWord не обязательно должно быть в wordList, но endWord должно.

Функция

ladderLength(beginWord: string, endWord: string, wordList: string-array) → integer

beginWordstring: первое слово лестницы
endWordstring: слово the ladder должно быть достигнуто
wordListstring-array: слова, из которых должен состоять каждый последующий шаг
Возвращаетinteger: количество слов в самой короткой цепочке преобразований или 0, если такой цепочки нет

Ограничения

1 ≤ beginWord.length ≤ 10
endWord и каждое слово в wordList имеют ту же длину, что и beginWord.
1 ≤ wordList.length ≤ 5000
Все слова состоят только из строчных букв английского алфавита.
beginWord != endWord
Все слова в wordList различны. beginWord может быть среди них, а может и не быть.

Примеры

Ввод: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Вывод: 4
Пояснение: lead и gold различаются тремя буквами, поэтому в любой цепочке не меньше 4 слов, а цепочка lead, load, goad, gold состоит ровно из 4 слов. lend и lewd тоже отличаются от lead одной буквой, но ни одно из них не ведёт к новым словам, а до bold можно добраться только от самого gold.

Ввод: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Вывод: 0
Пояснение: cat, cot, cog отличаются от dog всего на одну букву, но dog отсутствует в списке, поэтому никакая цепочка не может на нём закончиться.

Ввод: beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
Вывод: 3
Пояснение: ab, ad, cd и ab, cb, cd содержат по 3 слова. ab тоже есть в списке, но начальное слово в любом случае учитывается один раз.

+14 скрытых тестов при отправке

Дополнительный вопрос

Можешь вернуть одну из кратчайших цепочек слов целиком, слова по порядку, а не только её длину?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Рассматривай слова как узлы графа, а ребро соединяет два слова, различающиеся одной буквой. Тогда цепочка — это путь от beginWord до endWord, и все рёбра имеют одинаковую стоимость, поэтому кратчайшая цепочка — это путь с наименьшим числом рёбер. Именно это и находит поиск в ширину. Сложность задачи заключается в быстром поиске рёбер: сравнение каждой пары из 5,000 слов потребует 25 миллионов сравнений, поэтому в лучшем решении соседи ищутся с помощью шаблонов с подстановочными знаками. Ниже n — количество слов, а L — их длина.

Попробуй проверить каждую цепочку методом поиска в глубину

Верно, но не успевает на самых больших тестах

Идея

Начните с beginWord. Для текущего слова попробуйте каждое ещё не использованное слово, которое отличается на одну букву, и продолжите поиск из него. Достигнув endWord, запишите длину цепочки, если она самая короткая из найденных. Помечайте слова в текущем пути как использованные, чтобы цепочка не зацикливалась, и снова освобождайте каждое слово, когда возвращаетесь из него, чтобы его могли использовать другие цепочки. Как только найдётся цепочка из best слов, перестаньте продолжать любой путь, в котором уже best-1 слов: он не может завершиться цепочкой короче.

Это корректно, потому что алгоритм проверяет каждую цепочку, в которой слова не повторяются, а в кратчайшей цепочке повторов быть не может: если слово встречается дважды, удаление части между этими двумя вхождениями даст более короткую цепочку.

Алгоритм работает медленно, потому что количество цепочек растёт взрывным образом. Возьмём 26 слов, отличающихся только первой буквой: aaa, baa и так далее до zaa: любая пара отличается на одну букву, поэтому поиск может перебирать их в любом порядке, прежде чем перейти дальше, а 26 слов можно упорядочить примерно 4 × 10^26 способами. Отсечение помогает только после того, как найдена какая-то цепочка. Если достичь endWord вообще невозможно, отсечение никогда не сработает, и даже список из 34 слов уже превышает объём, который поиск успевает обработать. Рекурсия также уходит на глубину, равную длине цепочки, которая может составлять тысячи слов.

Алгоритм

Пометь beginWord как использованное, если оно есть в списке, и установи best равным 0.
Напиши search(word, length). Если word равно endWord, сохрани length, если оно меньше best, и вернись.
Если best не равно 0 и length + 1 ≥ best, вернись: этот путь не может привести к лучшему результату.
Для каждого неиспользованного слова, отличающегося от word на одну букву, пометь его как использованное, вызови search(next, length + 1), затем снова пометь его как неиспользованное.
Вызови search(beginWord, 1) и верни best, которое останется равным 0, если последовательности нет.

def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    best = 0  # words in the shortest sequence found so far, 0 while there is none
    used = [word == beginWord for word in wordList]  # words on the current path

    def search(word, length):
        nonlocal best
        if word == endWord:
            if best == 0 or length < best:
                best = length
            return
        if best != 0 and length + 1 >= best:
            return  # any longer path cannot beat the best one
        for i, candidate in enumerate(wordList):
            if not used[i] and one_letter_apart(word, candidate):
                used[i] = True
                search(candidate, length + 1)
                used[i] = False  # free the word for other paths

    search(beginWord, 1)
    return best

Поиск в ширину, сравнение каждой пары

Верно, но не успевает на самых больших тестах

Идея

Поиск в ширину исследует слова в порядке расстояния. Сначала beginWord — цепочка из 1 слова. Затем все слова, отличающиеся от него на одну букву, — цепочки из 2 слов. Затем каждое новое слово, отличающееся на одну букву от этих слов, — цепочки из 3 слов и так далее. Очередь сохраняет этот порядок: слова выходят из неё в том порядке, в котором они в неё попали, поэтому все слова на расстоянии d выходят раньше любого слова на расстоянии d + 1.

Именно поэтому первая цепочка, найденная поиском в ширину, будет кратчайшей. Когда слово впервые достигается на расстоянии d, все слова ближе, чем d, уже исследованы, поэтому, если бы до него существовала более короткая цепочка, поиск достиг бы этого слова раньше. По той же причине безопасно помечать слово как посещённое в момент добавления в очередь: его расстояние уже окончательное, а повторное достижение этого слова может дать только более длинный путь. Поэтому каждое слово попадает в очередь один раз, и как только endWord обнаруживается среди соседей, его расстояние становится ответом.

Эта версия находит соседей слова, сравнивая его с каждым словом в списке, буква за буквой, и останавливаясь при обнаружении второго различия. Для каждого из максимум n слов, выходящих из очереди, требуется n сравнений до L букв, итого O(n² × L). Для 5 000 слов и поиска, который посещает большую часть из них, это до 25 миллионов сравнений слов. Компилируемый язык справляется с этим быстро, но Python требуется несколько секунд на самом большом тесте.

Алгоритм

Если endWord нет в wordList, верни 0.
Помести beginWord в очередь с длиной 1. Отметь его как посещённое, если оно есть в списке.
Извлеки из очереди следующее слово и его длину.
Сравни его со всеми непосещёнными словами в списке. Для каждого слова, отличающегося ровно на одну букву: если это endWord, верни length + 1; иначе отметь его как посещённое и добавь в очередь с длиной length + 1.
Если очередь опустеет, endWord недостижимо: верни 0.

from collections import deque


def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    if endWord not in wordList:
        return 0
    visited = [word == beginWord for word in wordList]
    queue = deque([(beginWord, 1)])  # (word, words in the sequence up to it)
    while queue:
        word, length = queue.popleft()
        # Compare against every word to find the neighbours.
        for i, candidate in enumerate(wordList):
            if not visited[i] and one_letter_apart(word, candidate):
                if candidate == endWord:
                    return length + 1
                visited[i] = True
                queue.append((candidate, length + 1))
    return 0

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

Идея

Сохраним поиск в ширину и сделаем поиск соседей быстрым. Два слова отличаются ровно на одну букву, если при скрытии одной и той же позиции в обоих они становятся одинаковыми: hot и hit превращаются в h*t. Поэтому зададим для каждого слова L шаблонов — по одному для каждой скрытой позиции — и добавим слово в корзину для каждого шаблона. Соседи слова — это остальные слова в его L корзинах; их можно найти за L хеш-поисков вместо прохода по всему списку.

Вот как выполняется поиск на первом примере. Для lead получаются шаблоны *ead, l*ad, le*d и lea*. В корзине l*ad лежит load, а в корзине le*d — lend и lewd, поэтому уровень 2 состоит из этих трёх слов. Из load корзина *oad даёт goad на уровне 3, а из goad шаблон go*d даёт gold на уровне 4.

Ещё один способ сэкономить: когда корзина слова просмотрена, значит, уже достигнуты все слова в ней, поэтому очистим её. Позже другие слова с тем же шаблоном всё равно не найдут там ничего нового. В тесте, где aaa, baa и так далее до zaa имеют общий шаблон *aa, корзина из 26 слов просматривается один раз, а не 26 раз. Таким образом, поиск читает каждую из n × L записей в корзинах не более одного раза.

Для построения шаблонов требуется n × L строк длиной L букв, время и память O(n × L²), и поиск обходится столько же: каждое слово, извлекаемое из очереди, снова формирует свои L шаблонов. Для 5,000 слов длиной 10 букв это около 500,000 операций с буквами, тогда как попарное сравнение потребовало бы до 250 миллионов.

Алгоритм

Если endWord отсутствует в wordList, верните 0.
Для каждого слова в списке и для beginWord добавьте это слово в корзину для каждого из его L шаблонов.
Поместите beginWord в очередь, отметьте его как посещённое и задайте длину, равную 1.
Обрабатывайте очередь по одному уровню за раз. Если слово — это endWord, верните длину. В противном случае для каждого его шаблона добавьте в следующий уровень все непосещённые слова из соответствующей корзины, отметьте их как посещённые и очистите корзину.
После каждого уровня увеличивайте длину на 1. Если очередь опустеет, верните 0.

from collections import defaultdict, deque


def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    size = len(beginWord)
    # "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
    buckets = defaultdict(list)
    for word in set(wordList) | {beginWord}:
        for i in range(size):
            buckets[word[:i] + "*" + word[i + 1:]].append(word)
    visited = {beginWord}
    queue = deque([beginWord])
    length = 1  # words in the sequence up to the current level
    while queue:
        for _ in range(len(queue)):  # one level: every word at this distance
            word = queue.popleft()
            if word == endWord:
                return length
            for i in range(size):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbour in buckets[pattern]:
                    if neighbour not in visited:
                        visited.add(neighbour)
                        queue.append(neighbour)
                buckets[pattern] = []  # all of them are visited now: never scan it again
        length += 1
    return 0

Ловушки и крайние случаи

Большинство неправильных ответов возникает из-за того, что считают не то или неверно понимают правило для endWord.

Возвращают количество изменений вместо количества слов. Переход от lead к gold требует 3 изменений и 4 слов, поэтому ответ — 4.
Не проверяют, содержится ли endWord в wordList. Во втором примере поиск находит одно слово, отличающееся на одну букву от dog, но ответ равен 0.
Используют поиск в глубину и возвращают первую найденную цепочку. DFS проходит по одной ветви до конца, поэтому первая найденная цепочка часто оказывается длинной.
Помечают слово как посещённое, когда оно покидает очередь, а не когда добавляется в неё. Тогда слово из полной группы из 26 слов может попасть в очередь до 25 раз, и очередь вырастет намного больше, чем n.
Не помечают beginWord, если оно также содержится в wordList. Тогда поиск снова достигает его двумя уровнями позже и повторяет работу. Пометьте его как посещённое с самого начала.
Проверяют, отличаются ли слова не более чем одной буквой. Любое слово отличается от самого себя нулём букв, поэтому условие должно требовать ровно одну букву.
Рекурсивно проходят по цепочке. В одном скрытом тесте кратчайшая цепочка состоит из 1,500 слов — этого достаточно, чтобы в некоторых языках переполнить стек вызовов. Для BFS нужна только очередь.

Частые вопросы4

Почему поиск в ширину находит кратчайшую цепочку слов?

BFS исследует слова по раундам: сначала начальное слово, затем все слова, отличающиеся от него на одно изменение, а затем все слова, отличающиеся на два изменения. До слова впервые доходят в самом раннем раунде, в котором его можно достичь, поэтому расстояние до него равно наименьшему возможному числу изменений. Это работает только потому, что каждое изменение имеет одинаковую стоимость. Если бы стоимость каждого шага была разной, вместо этого понадобился бы алгоритм Дейкстры.

Какова временная сложность Word Ladder?

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

Как найти слова, отличающиеся на одну букву?

Один способ — использовать описанные выше корзины с подстановочными знаками: слова, соответствующие одному шаблону, например h*t, являются соседями. Другой способ — заменить каждую позицию в слове каждой из 26 букв и поискать полученный вариант в хеш-множестве слов. Для каждого слова это требует 26 × L поисков, каждый из которых хеширует L букв, то есть всего O(n × 26 × L²). Оба способа эффективнее, чем сравнение со всем списком.

Может ли двунаправленный BFS ускорить решение задачи Word Ladder?

Да. Одновременно выполняй поиск от beginWord и от endWord, каждый раз расширяя меньшую сторону на один уровень, и остановись, когда новая вершина уже достигнута с другой стороны. Тогда в цепочке будет на одно слово больше, чем суммарное количество изменений с обеих сторон. Если у каждого слова около b соседей, а для построения цепочки требуется d изменений, один поиск может затронуть около b^d слов, а два поиска, встретившиеся посередине, затронут около 2 × b^(d/2).

Python

def ladderLength(beginWord, endWord, wordList):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

beginWord = "lead"
endWord = "gold"
wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]

Ожидается

Word Ladder

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуй проверить каждую цепочку методом поиска в глубину

Поиск в ширину, сравнение каждой пары

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

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи