Word Search (LeetCode 79)

You get a 2D grid of letters, char[][] board, and a word. The question is whether the word can be spelled by walking from cell to cell, moving up, down, left or right, without using the same cell twice in one path.

For example, on this board:

A B C E
S F C S
A D E E

"ABCCED" is there: start at the top-left A, go right to B and C, down to C, then down to E and left to D. "SEE" is there too. But "ABCB" isn’t, since the only way back to that B is through a cell you’ve already used.

The idea

I try every cell as a starting point. From each one, dfs checks whether the current cell matches the next letter of the word, word.charAt(i). If it does, I mark the cell as used and try all four neighbors for letter i + 1. If i makes it all the way to word.length(), every letter matched, and the word is on the board.

The code

class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int currRow = 0; currRow < board.length; currRow++) {
            for (int currCol = 0; currCol < board[0].length; currCol++) {
                if (dfs(board, word, visited, 0, currRow, currCol)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, boolean[][] visited, int i, int currRow, int currCol) {
        if (i == word.length()) {
            return true;
        }
        if (currRow >= board.length || currCol >= board[0].length
                || currCol < 0 || currRow < 0
                || board[currRow][currCol] != word.charAt(i)
                || visited[currRow][currCol]) {
            return false;
        }
        visited[currRow][currCol] = true;
        boolean result = dfs(board, word, visited, i + 1, currRow - 1, currCol)
                || dfs(board, word, visited, i + 1, currRow, currCol - 1)
                || dfs(board, word, visited, i + 1, currRow, currCol + 1)
                || dfs(board, word, visited, i + 1, currRow + 1, currCol);
        visited[currRow][currCol] = false;
        return result;
    }
}

The || chain also does some work for free: as soon as one direction finds the rest of the word, Java stops evaluating, and the other directions never get tried.

The line I was missing

I found this problem tricky, and the reason was one line:

visited[currRow][currCol] = false;

My first version didn’t have it. I was marking cells as visited and never un-marking them, so I wasn’t doing the “undo” step that backtracking needs, and that broke my algorithm.

Here’s the thing: visited isn’t supposed to mean “I’ve ever been to this cell.” It’s supposed to mean “this cell is on the path I’m building right now.” The only reason it exists is so one path can’t use the same cell twice. Once dfs returns from a cell, that cell isn’t on the current path anymore, so it has to go back to unvisited. Otherwise it stays blocked for every path I try after that, even paths that never actually touched it.

Here’s the smallest board I could find where skipping that line gives the wrong answer:

B A
A A      word = "AAB"

The word is there: start at the bottom-right A, go left to the bottom-left A, then up to B. But without the un-mark:

1. The outer loop skips B, then starts at the top-right A. It goes down to the bottom-right A, but neither neighbor there is a B, so that path dies. Both of those As stay marked.
2. Next it starts at the bottom-left A. Its only A neighbor is the bottom-right one, which is still marked from step 1, so this path dies too.
3. Last is the bottom-right A, which is still marked from step 1, so it’s rejected right away.

Every starting point fails, and it returns false. With the un-mark, the cells from step 1’s dead end get released as it backs out, and the path from the bottom-right A finds the word.

This is exactly the opposite of Number of Islands, where I never un-mark a cell. There, visited really does mean “I’ve been here before.” A cell’s island never changes, and un-marking would make me count the same island twice. Here, a cell that was a dead end for one path might be exactly what another path needs. Same grid, same DFS, and the one line that’s different is the whole difference between flood fill and backtracking.

It’s the same add, recurse, undo pattern as N-Queens, Combination Sum and Subsets. The board is the thing I’m adding to and undoing this time, instead of a list.

Runtime

Let the board be $m \times n$ and let $L$ be the length of the word. Each of the $mn$ starting cells can launch a search. The first step can go 4 ways, and every step after that can go at most 3, since one direction is the cell I just came from, which is already marked. So one search tries at most about $4 \cdot 3^{L-1}$ paths, and the whole thing is $O(mn \cdot 3^L)$.

For space, visited takes $O(mn)$, and the recursion goes at most $L$ calls deep, so $O(L)$ on the stack.