Word Search

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

В худшем случае сложность составляет O(m·n·3^L) для доски размером m × n и слова длины L . Каждая из m·n ячеек может стать началом пути, а после первого шага у каждой ячейки есть не более трёх непосещённых соседей, которых можно проверить. Дополнительная память составляет O(L) для рекурсии и ещё O(m·n) , если вы копируете доску, чтобы пометить её.

СреднеПоиск с возвратом Графы

+10

Дана сетка букв board, представленная в виде списка строк, где board[r][c] — это буква в строке r, столбце c, а также строка word.

Верните true, если можно проследить word на сетке: начните с любой ячейки и на каждом шаге переходите в ячейку непосредственно выше, ниже, слева или справа от текущей, чтобы посещённые ячейки соответствовали буквам word по порядку. При таком обходе нельзя использовать одну и ту же ячейку дважды. В противном случае верните false. Регистр букв учитывается, поэтому a и A — разные символы.

Функция

exist(board: string-array, word: string) → boolean

boardstring-array: сетка, одна строка букв на каждую строку
wordstring: слово, которое нужно обвести
Возвращаетboolean: можно ли проследить слово по соседним ячейкам, используя каждую не более одного раза

Ограничения

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, и все строки имеют одинаковую длину.
1 ≤ word.length ≤ 20
board и word содержат только английские буквы в верхнем и нижнем регистре.

Примеры

Ввод: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Вывод: true
Пояснение: Начни с S в строке 0, столбце 0, затем иди вправо к T, вниз к O, вправо ко второй O, вправо к L и вниз к S в строке 2, столбце 3. Это шесть разных ячеек, каждая из которых соседствует с предыдущей.

Ввод: board = ["STAR", "POOL", "ENDS"]word = "POP"
Вывод: false
Пояснение: На доске есть только одна P — в строке 1, столбце 0. После P и O нужна ещё одна P, но единственная такая ячейка — та, с которой начался путь, а её нельзя использовать дважды.

Ввод: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Вывод: false
Пояснение: Каждая буква из SAND есть на доске, но путь обрывается на первом шаге: единственная A находится в строке 0, столбце 2, и ни одна из букв S не касается её.

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

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

Вместо ответа «да» или «нет» можешь посчитать, сколько разных вариантов провести word содержит доска?

Подсказки

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

Открыто 0 из 3

Решение

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

Поиск с возвратом с использованием сетки посещённых клеток

Идея

Представь дерево решений. Первый выбор — начальная клетка, и в ней должна быть word[0]. После этого каждый узел — это путь, который образует первые i букв, а его дочерние узлы — это соседние клетки, в которых находится word[i] и которые ещё не входят в путь. Путь, образующий всё слово, — это успех. Путь, у которого нет подходящего соседа, заходит в тупик, и ты возвращаешься назад, чтобы попробовать следующий вариант.

Сетка visited обеспечивает правило однократного использования. Отмечай клетку, когда путь заходит в неё, и снимай отметку, когда путь возвращается из неё. Именно снятие отметки и обеспечивает возврат с перебором: клетка, через которую проходил путь, зашедший в тупик, должна снова стать доступной для следующей попытки. На доске AA / AB со словом AAA, если начать с верхней левой клетки, движение вниз зайдёт в тупик в нижней левой клетке (её другой сосед — B), а движение вправо зайдёт в тупик в верхней правой клетке. Если бы эти клетки оставались отмеченными, ответ — нижняя левая, затем верхняя левая, затем верхняя правая — найти было бы невозможно.

Это стандартный ответ, и здесь он корректен и достаточно быстр. Его стоимость зависит от количества путей, которые он перебирает. После первого шага на каждом шаге есть не более трёх новых направлений, поэтому для слова из L букв может быть порядка m·n·3^L путей. Возьми доску 5 × 5, заполненную буквами A, и слово из 8 букв A, за которыми следует B. Каждый путь из букв A — допустимая начальная часть слова, и поиск проходит их все, прежде чем выясняет, что букв B нет: около 65,000 проверок клеток, чтобы получить ответ false. Каждая дополнительная буква примерно удваивает это число — поэтому в следующем подходе перед поиском выполняются несколько предварительных проверок.

Алгоритм

Создай сетку visited размером с игровое поле, заполни её значениями false.
Определи dfs(r, c, i): верни false, если (r, c) находится за пределами сетки, уже посещена или её буква не совпадает с word[i].
Если i — последний индекс в word, верни true.
Пометь (r, c) как посещённую, проверь четыре соседние ячейки с i+1, затем сними пометку и верни результат проверки, успешна ли хотя бы одна из соседних ячеек.
Вызови dfs(r, c, 0) для каждой ячейки и верни true, как только один из вызовов завершится успешно.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        visited[r][c] = True   # mark: the current path owns this cell
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        visited[r][c] = False  # restore: other paths may use it
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Возврат с отметками на месте и отсечением

Идея

Оставь тот же поиск и внеси два изменения. Во-первых, отмечай ячейки на приватной копии доски, а не в отдельной сетке: пока путь занимает ячейку, перезаписывай её символом #, а при возврате записывай букву обратно. # никогда не совпадает с буквой в слове, поэтому проверка букв также исключает ячейки на пути, а восстановление — это тот же шаг отмены, что и прежде.

Во-вторых, отсекай варианты до начала поиска. Посчитай буквы. Если для слова требуется больше экземпляров какой-либо буквы, чем есть на доске, ответ — false, и поиск не нужен. Так можно ответить для доски, состоящей только из A, с 8 символами A и одним B, вообще не выполняя поиск, вместо примерно 65 000 проверок. Начинай с более редкого конца. Путь, пройденный в обратном направлении, образует то же слово на тех же ячейках в обратном порядке, поэтому вместо исходного слова можно искать перевёрнутое. Если последняя буква встречается на доске реже первой, переверни слово. Поиск может начинаться с меньшего числа ячеек, а редкая буква отсеивает неверные начала на первом шаге, а не на последнем.

Второе правило особенно важно, если редкая буква есть на доске, но до неё нельзя добраться. Помести единственный B в угол, у которого два соседа — C, и ищи 8 символов A, а затем B. Проверка количества букв пройдёт. При поиске вперёд алгоритм всё равно обойдёт все пути из A — около 35 000 проверок ячеек. При поиске в обратном порядке слово начинается с B, начать можно только с одной ячейки, её соседи — не A, и поиск заканчивается примерно через 30 проверок.

Сложность в худшем случае всё ещё равна O(m·n·3^L): можно составить доску и слово так, чтобы буквы встречались равномерно, а тупики обнаруживались поздно. Отсечение не меняет ни ответ, ни асимптотическую оценку. Оно устраняет распространённые причины лишних затрат времени при обычном поиске ценой одного прохода для подсчёта букв, причём с увеличением длины слова разрыв быстро растёт.

Алгоритм

Подсчитай каждую букву на доске и в слове. Если для слова нужно больше экземпляров какой-либо буквы, чем есть на доске, верни false.
Если на доске больше экземпляров word[0], чем последней буквы, переверни word.
Скопируй доску в сетку символов, которую можно изменять.
Определи dfs(r, c, i): заверши неудачей, если ячейка не содержит word[i]; заверши успешно, если i — последний индекс; в противном случае установи в ячейке символ #, попробуй каждого соседнего элемента, находящегося в пределах сетки, с i+1, верни букву на место и верни, удалось ли хотя бы одно обращение.
Выполни dfs(r, c, 0) для каждой ячейки и верни true, как только один вызов завершится успешно.

from collections import Counter


def exist(board, word):
    rows, cols = len(board), len(board[0])

    # Pruning 1: the board must hold every letter as many times as the word uses it.
    have = Counter("".join(board))
    for letter, need in Counter(word).items():
        if have[letter] < need:
            return False

    # Pruning 2: a path read backwards is the same path, so start from the
    # end whose letter is rarer on the board: fewer cells begin a search.
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    grid = [list(row) for row in board]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if grid[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        grid[r][c] = "#"  # mark: "#" matches no letter, so this path cannot reuse the cell
        found = False
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                found = True
                break
        grid[r][c] = word[i]  # restore the letter for other paths
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

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

Большинство неправильных ответов связано с пометкой ячеек и проверкой границ.

Не снимают пометку с ячейки после неудачной ветви. Ячейка остаётся заблокированной для всех последующих путей, и для AA / AB слово AAA возвращает false.
Вообще не помечают ячейки. Без этого путь может вернуться на ячейку, с которой он начался, и POP на доске из примера вернёт true.
Сначала читают ячейку, а потом проверяют границы. В Python board[-1] — это последняя строка, а не ошибка, поэтому отсутствие проверки границ незаметно приводит к переходу через край сетки.
Проверяют успех только после хода. Однобуквенное слово на доске из одной ячейки, ["A"] со словом A, должно возвращать true, даже если у ячейки нет соседей.
Помечают ячейку символом, который может быть настоящей буквой. Например, изменение регистра ячейки приводит к ошибке на досках, где используются и a, и A.
Двигаются по диагонали. Соседними считаются только четыре ячейки, имеющие общую сторону.

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

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

В худшем случае сложность составляет O(m·n·3^L) для доски размером m × n и слова длины L. Каждая из m·n ячеек может стать началом пути, а после первого шага у каждой ячейки есть не более трёх непосещённых соседей, которых можно проверить. Дополнительная память составляет O(L) для рекурсии и ещё O(m·n), если вы копируете доску, чтобы пометить её.

Зачем снимать отметки с ячеек в поиске слов?

Отметка означает, что ячейка находится на текущем пути. Когда ветвь оказывается неудачной, ячейка покидает путь, и она может понадобиться для другого пути. Если оставить отметку, при последующих поисках ячейка будет считаться использованной, и можно не найти допустимое прохождение. Ставь отметку при входе, снимай при выходе.

Как прореживание ускоряет поиск слов?

Перед поиском выполняются две проверки. Если для слова требуется больше букв какого-либо типа, чем есть на доске, можно вернуть false, не выполняя поиск. А поскольку путь, прочитанный в обратном направлении, образует перевёрнутое слово, можно начать с того конца, где находится более редкая буква: так уменьшается количество начальных клеток и неправильные пути отбрасываются раньше. Ни одна из проверок не меняет худший случай, а обычный поиск и сам по себе даёт полный ответ. На доске 5 × 5, заполненной буквами A, при поиске слова, которому нужна отсутствующая B, они сокращают примерно 65 000 проверок клеток до нуля.

В чём разница между Word Search и Word Search II?

Word Search проверяет наличие одного слова. Word Search II получает список слов и проверяет, какие из них есть на доске. Если запускать этот поиск отдельно для каждого слова, много работы будет повторяться, поэтому обычно все слова помещают в префиксное дерево и обходят доску один раз, прекращая путь, как только выясняется, что ни одно слово не начинается с его букв.

Python

def exist(board, word):
    # Напишите код здесь

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

Случай 1

Случай 2

Случай 3

Ввод

board = ["STAR", "POOL", "ENDS"]
word = "STOOLS"

Ожидается

true