单词搜索

Problem

Given an \(m \times n\) grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "ABCCED"

Output: true

Example 2:

Input: board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "SEE"

Output: true

Example 3:

Input: board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "ABCB"

Output: false

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Idea

Try every cell as a starting point and run a depth-first search (DFS) with backtracking to match word one letter at a time, moving up, down, left, or right.

To make sure no cell is used twice in the same path, mark the current cell as visited before exploring its neighbors, and restore it when backtracking. Stop a branch as soon as the cell is out of bounds, already visited, or does not match the next letter.

Time complexity: \(O(m \cdot n \cdot 3^L)\), Space complexity: \(O(L)\), where \(L\) is the length of word (each step after the first has at most 3 unvisited directions, and the recursion depth is at most \(L\))

Pseudo Code

for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
        if (dfs(board, word, i, j, 0)) {
            return true;
        }
    }
}
return false;

boolean dfs(board, word, i, j, k) {
    if (k == word.length) {
        return true;
    }
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {
        return false;
    }
    temp = board[i][j];
    board[i][j] = '#';                 // mark as visited
    found = dfs(board, word, i + 1, j, k + 1)
         || dfs(board, word, i - 1, j, k + 1)
         || dfs(board, word, i, j + 1, k + 1)
         || dfs(board, word, i, j - 1, k + 1);
    board[i][j] = temp;                // restore when backtracking
    return found;
}