Поиск слова в матрице (DFS/backtracking по сетке)

O(mn*4^L)

Из каждой клетки DFS пытается сопоставить слово по буквам через соседей сверху-снизу-слева-справа, помечая клетку занятой и восстанавливая её при возврате, если путь не сработал. Это backtracking, где сама сетка выступает деревом решений.

Сигналы

существует ли слово как путь по доскепроследить буквы через соседние клетки без повторовDFS с возвратом (backtracking) по сеткепометить клетку посещённой, затем отменить пометку

Шаблон

function exist(board, word) {
    const rows = board.length, cols = board[0].length;
    function dfs(r, c, i) {
        if (i === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) return false;
        const tmp = board[r][c];
        board[r][c] = "#";
        const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) ||
                      dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
        board[r][c] = tmp;
        return found;
    }
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

Похоже, но не то

Backtracking: Обычный backtracking перебирает список решений, например, какое подмножество или перестановку строить дальше. Поиск слова на сетке использует тот же цикл выбор/исследование/отмена, но сама сетка выступает списком решений: в каждой клетке пробуются до четырёх соседних направлений, клетка помечается занятой и восстанавливается при возврате.

сетка до ~6x6..12x12 и длина слова L до ~10, DFS с 4 ветвями на шаг из каждой стартовой клетки -> O(mn * 4^L): доминирует именно backtracking, а не сам размер сетки.

Изучить этот паттерн