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

By | August 5, 2024

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

For example, given the following board:

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

```

`exists(board, "ABCCED")` returns `true``exists(board, "SEE")` returns `true``exists(board, "ABCB")` returns `false`.

Python

`def exist(board, word):    if not board:        return False    def dfs(board, word, i, j, k):        if k == len(word):            return True        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:            return False                temp = board[i][j]        board[i][j] = '#'  # mark as visited        res = (dfs(board, word, i+1, j, k+1) or               dfs(board, word, i-1, j, k+1) or               dfs(board, word, i, j+1, k+1) or               dfs(board, word, i, j-1, k+1))        board[i][j] = temp  # unmark        return res    for i in range(len(board)):        for j in range(len(board[0])):            if dfs(board, word, i, j, 0):                return True    return False# Example usageboard = [  ['A','B','C','E'],  ['S','F','C','S'],  ['A','D','E','E']]print(exist(board, "ABCCED"))  # returns Trueprint(exist(board, "SEE"))  # returns Trueprint(exist(board, "ABCB"))  # returns False`

Java

`public class Solution {    public boolean exist(char[][] board, String word) {        if (board == null || board.length == 0) return false;        for (int i = 0; i < board.length; i++) {            for (int j = 0; j < board[0].length; j++) {                if (dfs(board, word, i, j, 0)) {                    return true;                }            }        }        return false;    }    private boolean dfs(char[][] board, String word, int i, int j, int k) {        if (k == word.length()) return true;        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) {            return false;        }        char temp = board[i][j];        board[i][j] = '#';  // mark as visited        boolean res = 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;  // unmark        return res;    }    public static void main(String[] args) {        Solution solution = new Solution();        char[][] board = {            {'A','B','C','E'},            {'S','F','C','S'},            {'A','D','E','E'}        };        System.out.println(solution.exist(board, "ABCCED"));  // returns True        System.out.println(solution.exist(board, "SEE"));  // returns True        System.out.println(solution.exist(board, "ABCB"));  // returns False    }}`

Javascript:

`var exist = function(board, word) {    if (!board || board.length === 0) return false;    function dfs(board, word, i, j, k) {        if (k === word.length) return true;        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] !== word[k]) {            return false;        }        const temp = board[i][j];        board[i][j] = '#';  // mark as visited        const res = 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;  // unmark        return res;    }    for (let i = 0; i < board.length; i++) {        for (let j = 0; j < board[0].length; j++) {            if (dfs(board, word, i, j, 0)) {                return true;            }        }    }    return false;};// Example usageconst board = [  ['A','B','C','E'],  ['S','F','C','S'],  ['A','D','E','E']];console.log(exist(board, "ABCCED"));  // returns trueconsole.log(exist(board, "SEE"));  // returns trueconsole.log(exist(board, "ABCB"));  // returns false`

Asked by Coursera.