> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/word-search-board.md).

# Word Search Board

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where `"adjacent"` cells are those horizontally or vertically neighboring. The cell itself does not count as an adjacent cell.\
The same letter cell may be used more than once.

**Example :**

Given board =

```
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
```

```
word = "ABCCED", -> returns 1,
word = "SEE", -> returns 1,
word = "ABCB", -> returns 1,
word = "ABFSAB" -> returns 1
word = "ABCD" -> returns 0
```

Note that 1 corresponds to true, and 0 corresponds to false.

```java
public class Solution {
    public int exist(String[] A, String B) {
        if (B.length() == 0)
            return 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A[i].length(); j++) {
                if (A[i].charAt(j) == B.charAt(0)) {
                    boolean ans = DFS(A, B, i, j, 0);
                    if (ans)
                        return 1;
                }
            }
        }
        return 0;
    }

    public boolean DFS(String[] A, String B, int x, int y, int index) {
        if (x >= 0 && x < A.length && y >= 0 && y < A[x].length() && A[x].charAt(y) == B.charAt(index)) {
            if (index == B.length() - 1)
                return true;
            return DFS(A, B, x + 1, y, index + 1)
                || DFS(A, B, x - 1, y, index + 1) 
                || DFS(A, B, x, y + 1, index + 1)
                || DFS(A, B, x, y - 1, index + 1);
        }
        return false;
    }
}

```