Problem Explanation

We are given a 2D grid of characters and a string word. We need to determine if the word exists in the grid. A word is valid if consecutive characters of the word exist in sequential, either horizontally or vertically.

For example, let's take a look at this board:

1
2
3[
4  ['A','B','C','E'],
5  ['S','F','C','S'],
6  ['A','D','E','E']
7]

The word "ABCCED" exists in the board since we can traverse from 'A'->'B'->'C'->'C'->'E'->'D'.

The word "SEE" also exists since we can traverse from 'S'->'E'->'E'.

The word "ABCB" does not exist in the board because 'B' cannot be reached from 'C' in the last traversal.

Solution Approach

The strategy we will use to solve this problem is depth-first search (DFS). DFS is a searching algorithm that explores as far as possible along each branch before backtracking. For our problem, we will start from each cell in the 2D grid and check if the current cell character matches the first character of the word. If it matches, we use DFS to explore all of its neighbors (up, down, left, right), moving to the next character in the word. To avoid visiting a cell twice, we temporarily mark it as visited during the DFS using some character that doesn't exist in the grid(like "*"). If we find the whole word, we return true. If the word does not exist, we backtrack, unmark the cell, and continue to the next cell.

Solution in Python

1
2Python
3class Solution:
4	def exist(self, board, word):
5		if not board:
6			return False
7		for i in range(len(board)):
8			for j in range(len(board[0])):
9				if self.dfs(board, i, j, word):
10					# If the word exists, return True
11					return True
12		# If the word doesn't exist in the grid, return False
13		return False
14	
15	def dfs(self, board, i, j, word):
16		# If we have found the word
17		if len(word) == 0:
18			return True
19		if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0] != board[i][j]:
20			return False
21		tmp = board[i][j]
22		board[i][j] = "#"
23		# Find the word in the neighbors
24		res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \
25			or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
26		board[i][j] = tmp
27		return res

Solution in Java

1
2Java
3public class Solution {
4    public boolean exist(char[][] board, String word) {
5        if (board.length == 0) {
6            return false;
7        }
8        for (int i = 0; i < board.length; i++) {
9            for (int j = 0; j < board[0].length; j++) {
10                if (dfs(board, i, j, word, 0)) {
11                    // If the word exists, return true
12                    return true;
13                }
14            }
15        }
16        // If the word does not exist, return false
17        return false;
18    }
19
20    private boolean dfs(char[][] board, int i, int j, String word, int k) {
21        if (i < 0 || j < 0 || i == board.length || j == board[0].length || board[i][j] != word.charAt(k)) {
22            return false;
23        }
24        if (k == word.length() - 1) {
25            return true;
26        }
27        char temp = board[i][j];
28        board[i][j] = '/';
29        boolean res = dfs(board, i+1, j, word, k+1) || dfs(board, i-1, j, word, k+1) ||
30                      dfs(board, i, j+1, word, k+1) || dfs(board, i, j-1, word, k+1);
31        board[i][j] = temp;
32        return res;
33    }
34}

In both Python and Java solutions, the algorithm iterates over every cell in the input grid and runs a Depth-First Search to determine if a valid word exists from that particular cell. This approach ensures that all possible words starting from each cell are checked. The runtime complexity of this solution is O(N * 4^L) where N is the number of cells in the grid and L is the length of the word to be matched.## Solution in JavaScript

In the following JavaScript solution, we use the same strategy of DFS to search for the word in the grid. Here is the code snippet for the solution:

1
2JavaScript
3var exist = function(board, word) {
4    for (let i = 0; i < board.length; i++) {
5        for (let j = 0; j < board[0].length; j++) {
6            if (dfs(board, word, i, j, 0)) {
7                // If the word exist, return true
8                return true;
9            } 
10        }
11    }
12    // If the word doesn't exist in the grid, return false
13    return false;
14};
15        
16var dfs = function(board, word, row, col, index) {
17    if (index == word.length) {
18        return true;
19    }
20    if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || board[row][col] !== word[index]) {
21        return false;
22    }
23
24    let temp = board[row][col];
25    board[row][col] = '-';
26    let exists = dfs(board, word, row+1, col, index+1) || dfs(board, word, row-1, col, index+1) ||
27                  dfs(board, word, row, col+1, index+1) || dfs(board, word, row, col-1, index+1);
28    board[row][col] = temp;
29    return exists;
30};

JavaScript solution mimics the Python and Java solution strategy. It defines a helper function for DFS (dfs) and calls it for each cell in the grid. This solution will traverse in four directions(left, right, up, down) and uses index to match the word character in DFS. If match found it will keep on traversing for the next character else it will return false back to the main function which will start traversing from the next index. The same process continues until all cells in the grid are traversed and word is matched or not.

The JavaScript solution also has a time complexity of O(N * 4^L), where N is the number of cells in the grid and L is the length of the word, for the same reasons as the Python and Java solutions.