Word Search

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

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

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

+10

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

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

Функция

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, двигайтесь вправо к T, вниз к O, вправо к O и L, а затем вниз к S под L. Ни одна ячейка не повторяется.

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

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

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

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

Подсказки

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

Открыто 0 из 3

Решение

Тебе нужно найти пути по сетке. При поиске с возвратом путь строится по одной букве за раз: каждая ячейка помечается, пока входит в путь, и снимается с отметки при возврате, поэтому ни один путь не использует ячейку повторно. Поиск имеет экспоненциальную сложность относительно длины слова, что допустимо для поля 6 × 6.

Возврат с сеткой посещённых клеток

Идея

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

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

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

Алгоритм

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

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, не выполняя поиск. Если прочитать путь в обратном направлении, на тех же клетках получится перевёрнутое слово, поэтому поиск перевёрнутого слова даст тот же ответ. Начинайте с того конца, буква которого встречается на доске реже: клеток, с которых можно начать, будет меньше, и неподходящие начальные клетки сразу отсеются.

Если единственная B находится в углу между двумя C, прямой поиск выполняет около 35 000 проверок клеток; поиск в обратном направлении — 27. Худший случай по-прежнему O(m·n·3^L).

Алгоритм

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

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

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

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

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

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

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

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

Сначала посчитайте буквы и верните false, если на доске слишком мало букв одного из видов. Затем ищите с конца, начиная с более редкой буквы, с которой могут начинаться меньше клеток. Ни одна из проверок не меняет худший случай.

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

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

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

Тест #1

Тест #2

Тест #3

Аргументы

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

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

true