> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/graph-search/search-in-a-grid/word-search.md).

# Word Search

## Question ([LC.79](https://leetcode.com/problems/word-search/))

> Given a 2D board and a target word, check if the target word is in the board.

Edges are horizontal and vertical

## Example

```
Board
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

(board, "ABFD") => true
(board, "SEE") => true
(board, "ABFA") => false
```

## Approach

We want to find a valid *path*. BFS is designed for layer search. Path search is DFS's job.

## DFS Code

```java
public boolean exist(char[][] board, String query) {
    int m = board.length;
    int n = board[0].length;
    boolean[][] visited = new boolean[m][n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (dfsWord(board, visited, query, 0, new Pos(i,j)))
                return true;
    return false;
}

// dfs on suffix
private boolean dfsWord(char[][] board, 
                        boolean[][] visited, 
                        String query,
                        int charPos,
                        Pos current) {
    // base case 1. out of bound 2. does not match char 3. visited 4. full match
    if (!inBound(board, current)) return false;
    if (visited[current.row][current.col]) return false;
    if (board[current.row][current.col] != query.charAt(charPos)) return false;
    if (charPos == query.length() - 1) return true;
    // previsit
    visited[current.row][current.col] = true;
    // dfs try all paths
    for (int p = 0; p < 4; p++) {
        Pos neighbor = new Pos(current.row + drow[p], current.col + dcol[p]);
        if (dfsWord(board, visited, query, charPos + 1, neighbor)) {
            return true;
        }
    }
    // postvisit
    visited[current.row][current.col] = false;
    return false; // all paths failed
}
```

## Time Complexity

The worst case is an exhaustive search so exponential time. O(4^len(word)).

## Word Search II ([LC.212](https://leetcode.com/problems/word-search-ii/description/))

Use a trie to accelerate the prefix search