Matrix word search (grid DFS/backtracking)

How does Matrix word search (grid DFS/backtracking) work?

Any cell can start the word. Try the search from each of them.

At a cell, compare it with the current character. A mismatch ends this branch at once.

Mark the cell as used before stepping onward. Otherwise the path can walk over itself.

Try each of the four neighbours in turn. Any of them might continue the word.

Unmark the cell after all four calls return. The next search has to see it free.

Reaching the end of the word is success. Nothing below that point matters.

Sources: Wikipedia: Backtracking

1. start at A, index 0The grid is A, B over C, D and the word is ABD.
2. neighbour B, index 1B matches the second letter, so it is marked too.
3. from B: A is markedThe mark is what stops the path from turning back.
4. D, index 2D matches the last letter. The word is complete.
5. answer = trueTwo cells were marked, and both clear on the way out.

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;
    }

A worked example of Matrix word search (grid DFS/backtracking)

Find every word hidden in a grid

You get a grid of letters and a list of words. Return every word the grid contains.

Searching each word separately repeats an enormous amount of work.

Put all the words into a trie first.

Then walk the grid once, carrying a trie node instead of a word index. A missing child prunes the branch.

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;
}

When should you use Matrix word search (grid DFS/backtracking)?

Use Matrix word search (grid DFS/backtracking) when the problem statement says “does the word exist as a path on the board”, “trace letters through adjacent cells, no reuse” or “DFS with backtracking on a grid”. A solution built on it usually runs in O(mn*4^L).

• •does the word exist as a path on the board
• •trace letters through adjacent cells, no reuse
• •DFS with backtracking on a grid
• •mark a cell as visited, then undo it

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Matrix word search (grid DFS/backtracking) confused with?

Matrix word search (grid DFS/backtracking) is most often confused with Backtracking, Graph BFS / DFS, Connected components and Trie (prefix tree).

• Backtracking: This is backtracking with the grid as the tree. The choices are the four neighbours.
• Graph BFS / DFS: A traversal marks a cell once and forever. Here the mark comes off on the way out.
• Connected components: Flood fill also walks neighbours, but it never unmarks. It is counting rather than searching.
• Trie (prefix tree): With many words to find, a trie prunes the walk. Without one each word costs its own search.

Common mistakes with Matrix word search (grid DFS/backtracking)

• Forgetting to unmark the cell

  A marked cell then stays blocked for every later search. Restore it after the four calls return.

• Marking with a real letter

  A marker that can appear in a word lets the path reuse a cell. Pick a character the alphabet never holds.

• Checking the bounds after reading

  Reading outside the grid throws or gives undefined. Test the coordinates before touching them.

• Searching each word on its own

  A hundred words means a hundred full walks. One trie collapses them into a single walk.

Which interview problems use Matrix word search (grid DFS/backtracking)?

Interview problems solved with Matrix word search (grid DFS/backtracking) include Word search, Word search II, Number of islands, Path with maximum gold, Unique paths III, Rat in a maze and Sudoku solver.

• Word search: One word, four neighbours at every step.
• Word search II: A trie prunes the walk when there are many words.
• Number of islands: The same walk, except it never unmarks.
• Path with maximum gold: Collect the value, then restore it on the way out.
• Unique paths III: Every free cell has to be visited exactly once.
• Rat in a maze: The same shape, but the path itself is recorded.
• Sudoku solver: A grid where the choices are digits, not directions.

What is the time and space complexity of Matrix word search (grid DFS/backtracking)?

The target complexity of Matrix word search (grid DFS/backtracking) is O(mn*4L).

An r by c grid with a word of length L costs O(rc times 4^L). Pruning is what makes it run.