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.

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

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)?

These phrases in a problem statement point here:

• •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

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

• 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

  It 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)?

• 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)?

O(mn*4^L)

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