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

Matrix word search (grid DFS/backtracking)

O(mn*4^L)

Ищите в сетке, шагая в соседа и потом возвращаясь обратно. Клетка помечена ровно столько времени, сколько вы внутри неё.

Elman HuseynovОбновлено 29 окт. 2026 г.

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

Слово может начинаться в любой клетке. Пробуйте поиск из каждой.

В клетке сравните её с текущим символом. Несовпадение сразу обрывает эту ветку.

Пометьте клетку использованной до шага дальше. Иначе путь пройдёт сам по себе.

Попробуйте по очереди всех четырёх соседей. Слово может продолжиться через любого.

Снимите пометку после возврата всех четырёх вызовов. Следующий поиск обязан увидеть клетку свободной.

Дойти до конца слова значит найти его. Ниже этой точки ничего не важно.

Источники: Википедия: Поиск с возвратом

старт в A, индекс 0Сетка это A, B над C, D, а слово это ABD.
сосед B, индекс 1B совпадает со второй буквой, поэтому тоже помечается.
из B: A помеченаИменно пометка не даёт пути повернуть назад.
D, индекс 2D совпадает с последней буквой. Слово собрано.
ответ = истинаПомечены были две клетки, и обе очищаются на выходе.

Поиск слова "TOP" на сетке букв

exist([["C", "A", "T", "S"], ["A", "X", "T", "O"], ["T", "O", "P", "S"]], "TOP")

board (подсвечены клетки текущего пути)

	0	1	2	3
0	C	A	T	S
1	A	X	T	O
2	T	O	P	S

word

TOP

i = 0path = -

Можно ли пройти "TOP" по соседним клеткам доски, не беря ни одну клетку дважды? Пробуем начать с каждой клетки по очереди.

1 / 28

Поиск слова в матрице (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;
}

function exist(board: string[][], word: string): boolean {
    const rows = board.length, cols = board[0].length;
    function dfs(r: number, c: number, i: number): boolean {
        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;
}

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

    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False
        tmp, board[r][c] = board[r][c], "#"
        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))
        board[r][c] = tmp
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

function exist(array &$board, string $word): bool {
    $rows = count($board); $cols = count($board[0]);
    $dfs = function (int $r, int $c, int $i) use (&$board, &$dfs, $word, $rows, $cols): bool {
        if ($i === strlen($word)) return true;
        if ($r < 0 || $r >= $rows || $c < 0 || $c >= $cols || $board[$r][$c] !== $word[$i]) return false;
        $tmp = $board[$r][$c];
        $board[$r][$c] = "#";
        $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 ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($dfs($r, $c, 0)) return true;
        }
    }
    return false;
}

    public static boolean exist(char[][] board, String word) {
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }

    private static boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
                || board[r][c] != word.charAt(i)) return false;
        char tmp = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, r + 1, c, i + 1) || dfs(board, word, r - 1, c, i + 1)
                || dfs(board, word, r, c + 1, i + 1) || dfs(board, word, r, c - 1, i + 1);
        board[r][c] = tmp;
        return found;
    }

    public static bool Exist(char[][] board, string word) {
        for (int r = 0; r < board.Length; r++) {
            for (int c = 0; c < board[0].Length; c++) {
                if (Dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }

    private static bool Dfs(char[][] board, string word, int r, int c, int i) {
        if (i == word.Length) return true;
        if (r < 0 || r >= board.Length || c < 0 || c >= board[0].Length
                || board[r][c] != word[i]) return false;
        char tmp = board[r][c];
        board[r][c] = '#';
        bool found = Dfs(board, word, r + 1, c, i + 1) || Dfs(board, word, r - 1, c, i + 1)
                || Dfs(board, word, r, c + 1, i + 1) || Dfs(board, word, r, c - 1, i + 1);
        board[r][c] = tmp;
        return found;
    }

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

Найти все слова, спрятанные в сетке

Даны сетка букв и список слов. Верните все слова, которые есть в сетке.

Поиск каждого слова по отдельности повторяет огромный объём работы.

Сначала сложите все слова в trie.

Потом пройдите сетку один раз, неся узел trie вместо индекса в слове. Отсутствующий потомок обрезает ветку.

function findWords(board, words) {
    const root = { children: {} };
    for (const word of words) {
        let node = root;
        for (const c of word) {
            node.children[c] = node.children[c] ?? { children: {} };
            node = node.children[c];
        }
        node.word = word;
    }

    const found = [];

    function walk(r, c, node) {
        const letter = board[r]?.[c];
        const next = letter && node.children[letter];
        if (!next) return; // no word continues this way

        if (next.word) {
            found.push(next.word);
            next.word = null; // never report the same word twice
        }

        board[r][c] = "#"; // marked only while we are inside this cell
        walk(r + 1, c, next);
        walk(r - 1, c, next);
        walk(r, c + 1, next);
        walk(r, c - 1, next);
        board[r][c] = letter;
    }

    for (let r = 0; r < board.length; r++) {
        for (let c = 0; c < board[0].length; c++) walk(r, c, root);
    }

    return found;
}

Поиск слова в матрице (DFS/backtracking по сетке): когда применять?

Паттерн «Поиск слова в матрице (DFS/backtracking по сетке)» нужен, когда в условии есть слова «существует ли слово как путь по доске», «проследить буквы через соседние клетки без повторов» или «DFS с возвратом (backtracking) по сетке». Решение на нём обычно укладывается в O(mn*4^L).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Поиск слова в матрице (DFS/backtracking по сетке): с чем путают?

Паттерн «Поиск слова в матрице (DFS/backtracking по сетке)» чаще всего путают с этими паттернами: Бэктрекинг, Обход графа BFS / DFS, Компоненты связности и Trie (префиксное дерево).

Бэктрекинг (Backtracking): Это бэктрекинг по сетке вместо дерева. Варианты хода это четыре соседа.
Обход графа BFS / DFS (Graph BFS / DFS): Обход помечает клетку раз и навсегда. Здесь пометка снимается на выходе.
Компоненты связности (Connected components): Заливка тоже ходит по соседям, но пометки не снимает. Она считает, а не ищет.
Trie (префиксное дерево) (Trie (prefix tree)): Когда слов много, trie обрезает обход. Без него каждое слово стоит своего поиска.

Поиск слова в матрице (DFS/backtracking по сетке): частые ошибки

Забывают снять пометку
Клетка остаётся закрытой для всех последующих поисков. Восстанавливайте её после четырёх вызовов.
Помечают настоящей буквой
Метка, которая встречается в словах, позволяет пути пройти клетку заново. Возьмите символ вне алфавита.
Проверяют границы после чтения
Чтение вне сетки падает или даёт undefined. Проверяйте координаты до обращения.
Ищут каждое слово отдельно
Сто слов означают сто полных обходов. Один trie сводит их к единственному обходу.

Паттерн «Поиск слова в матрице (DFS/backtracking по сетке)» решает такие задачи с собеседований: Поиск слова в сетке, Поиск слов в сетке II, Число островов, Путь с наибольшим золотом, Уникальные пути III, Крыса в лабиринте и Решатель судоку.

Поиск слова в сетке: Одно слово, четыре соседа на каждом шаге.
Поиск слов в сетке II: Trie обрезает обход, когда слов много.
Число островов: Тот же обход, только пометки не снимаются.
Путь с наибольшим золотом: Соберите значение и верните его на выходе.
Уникальные пути III: Каждую свободную клетку надо посетить ровно один раз.
Крыса в лабиринте: Та же форма, но записывается сам путь.
Решатель судоку: Сетка, где варианты это цифры, а не направления.