Поиск заданного слова в двумерной решётке

Условие

Дана двумерная решётка размером m × n, заполненная символами board, и строка word. Требуется реализовать функцию, которая возвращает True, если слово word можно собрать, перемещаясь по последовательным соседним ячейкам (соседями считаются клетки, расположенные горизонтально или вертикально рядом). При этом одну и ту же ячейку нельзя использовать более одного раза.

Пример 1: Ввод: board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED" Вывод: True

Пример 2: Ввод: board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE" Вывод: True

Пример 3: Ввод: board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB" Вывод: False

Ответ

Запускайте поиск в глубину из каждой подходящей клетки и отмечайте клетки текущего пути. При возврате снимайте отметку, чтобы другие пути могли их использовать; повтор внутри одного пути запрещён.

Решение для прямоугольной доски:

def exists(board, word):
    if not word:
        return True
    if not board or not board[0]:
        return False
    rows, cols = len(board), len(board[0])
    if len(word) > rows * cols:
        return False
    used = set()
    def search(r, c, index):
        if not (0 <= r < rows and 0 <= c < cols):
            return False
        if (r, c) in used or board[r][c] != word[index]:
            return False
        if index == len(word) - 1:
            return True
        used.add((r, c))
        found = any(search(r + dr, c + dc, index + 1)
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        used.remove((r, c))
        return found
    return any(search(r, c, 0) for r in range(rows) for c in range(cols))

В худшем случае поиск экспоненциальный по длине слова. Глубина рекурсии и память пути O(len(word)); для очень длинного слова потребуется явный стек.