mediumBacktracking

Word Search

Determine whether a word can be traced through a board using horizontal or vertical neighbors. Do not reuse a cell within the path.

LeetCode ↗

Work through the cases

3 examples

Input notation

Word on line 1; rectangular board rows as contiguous letters on subsequent lines.

Expected result

true or false.

Case 1

Input

ABDC
AB
CD

Expected output

true

Case 2

Input

ABA
AB
CD

Expected output

false

Case 3

Input

A
A

Expected output

true

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

From every cell, walk length-|word| paths and compare. At most 36 cells and |word| ≤ 15, unpruned search explodes. Match while walking, abort on mismatch, and never reuse a cell. Enumerate starts; dfs(i,j,k) means (i,j) should match word[k]. On match, write '0' to block re-entry, try four neighbors at k+1, then restore. Letters are never '0', so no extra vis. Any successful start is enough.

We can enumerate each position (i, j) in the grid as the starting point of the search, and then start a depth-first search from the starting point. If we can search to the end of the word, it means the word exists, otherwise, it means the word does not exist.

Therefore, we design a function dfs(i, j, k), which represents whether we can successfully search from the (i, j) position of the grid, starting from the kth character of the word. The execution steps of the function dfs(i, j, k) are as follows:

- If k = |word|-1, it means that we have searched to the last character of the word. At this time, we only need to judge whether the character at the (i, j) position of the grid is equal to word[k]. If they are equal, it means the word exists, otherwise, it means the word does not exist. Whether the word exists or not, there is no need to continue to search, so return the result directly. - Otherwise, if the word[k] character is not equal to the character at the (i, j) position of the grid, it means that the search failed this time, so return false directly. - Otherwise, we temporarily store the character at the (i, j) position of the grid in c, and then modify the character at this position to a special character '0', indicating that the character at this position has been used to prevent it from being reused in subsequent searches. Then we start from the up, down, left, and right directions of the (i, j) position to search for the k+1th character in the grid. If any direction is successful, it means the search is successful, otherwise, it means the search failed. At this time, we need to restore the character at the (i, j) position of the grid, that is, put c back to the (i, j) position (backtracking).

In the main function, we enumerate each position (i, j) in the grid as the starting point. If calling dfs(i, j, 0) returns true, it means the word exists, otherwise, it means the word does not exist, so return false.

The time complexity is O(m × n × 3^k), and the space complexity is O(\min(m × n, k)). Here, m and n are the number of rows and columns of the grid, respectively; and k is the length of the string word.

class Solution {
    private int m;
    private int n;
    private String word;
    private char[][] board;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        this.word = word;
        this.board = board;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int i, int j, int k) {
        if (k == word.length() - 1) {
            return board[i][j] == word.charAt(k);
        }
        if (board[i][j] != word.charAt(k)) {
            return false;
        }
        char c = board[i][j];
        board[i][j] = '0';
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int u = 0; u < 4; ++u) {
            int x = i + dirs[u], y = j + dirs[u + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' && dfs(x, y, k + 1)) {
                return true;
            }
        }
        board[i][j] = c;
        return false;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.