Word Ladder

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

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

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

+10

Тебе даны два слова — beginWord и endWord — и список слов wordList. Лесенка начинается с beginWord, заканчивается endWord, и в каждом следующем слове меняется ровно одна буква. Каждое слово после beginWord должно быть из wordList, поэтому endWord обязательно должно быть в этом списке; beginWord может в нём отсутствовать.

Верни количество слов в кратчайшей лесенке, включая оба конца, или 0, если такой лесенки нет.

Функция

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

beginWordstring: первое слово в лестнице
endWordstring: слово, которого должна достичь лестница
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 — тупиковые варианты.

Ввод: 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 также есть в списке, но начальное слово учитывается один раз.

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

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

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

26 слов aaa, baa и так далее до zaa отличаются друг от друга на одну букву, и их можно упорядочить примерно 4 × 10^26 способами. Если endWord недостижимо, отсечение никогда не срабатывает, и поиск перебирает их все.

Алгоритм

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

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

Поиск в ширину, сравнивая каждую пару

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

Идея

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

В этой версии поиск соседей слова выполняется сравнением его со всеми словами в списке до обнаружения второго различия: O(n² × L), до 25 миллионов сравнений слов для 5 000 слов.

Алгоритм

Если endWord отсутствует в wordList, верни 0.
Добавь beginWord в очередь с длиной 1, отметив его как посещённое, если оно есть в списке.
Возьми следующее слово и сравни его со всеми непосещёнными словами. Для каждого слова, отличающегося на одну букву: если это endWord, верни длину + 1; иначе отметь его и добавь в очередь с длиной + 1.
Если очередь опустеет, верни 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 хеш-поисков вместо перебора всего списка.

В первом примере в l*ad находятся load, а в le*d — lend и lewd, поэтому уровень 2 — это все три слова; затем по *oad находится goad, а по go*d на уровне 4 находится gold.

После просмотра корзины до всех слов в ней уже добрались, поэтому очисти её: корзину из 26 слов *aa просматривают один раз, а не 26 раз. Затраты времени и памяти составляют O(n × L²) — около 500 000 проверок букв для 5 000 слов длиной 10 букв.

Алгоритм

Если 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

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

Подсчёт изменений вместо слов. От lead до gold — 3 изменения и 4 слова; ответ — 4.
Пропуск проверки того, что endWord входит в wordList. Во втором примере можно добраться до cog, отличающегося от dog одной буквой, но ответ равен 0.
Пометка слова как посещённого, когда оно покидает очередь. Тогда к слову в корзине *aa можно присоединиться до 25 раз, и очередь вырастет намного больше n.
Рекурсивный обход цепочки. Кратчайшая цепочка может состоять из тысяч слов — этого достаточно, чтобы переполнить стек вызовов.

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

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

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

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

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

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

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

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

Тест #1

Тест #2

Тест #3

Аргументы

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

Ожидаемый вывод

Word Ladder

Функция

Ограничения

Примеры

Подсказки

Решение

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

Поиск в ширину, сравнивая каждую пару

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

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

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

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