# Word search in JavaScript

Welcome to another installment of our LeetCode problem-solving series! In this post, we’ll dive into solving LeetCode Problem 79 – “Word Search” using JavaScript. This problem challenges us to determine if a given word exists in a 2D board of characters. Join us as we break down the problem, explore our approach, and provide a step-by-step solution.

Given an `m x 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.

##### Difficulty Level: Medium

**Approach to solving word search problem:**

Before we jump into the code, let’s outline our approach:

- We’ll iterate through each cell of the board and start a depth-first search (DFS) for the target word.
- If the current cell’s character matches the first letter of the word, we’ll start the DFS from that cell.
- During the DFS, we’ll check adjacent cells for the next character in the word.
- If we can’t find a match, we’ll backtrack and continue searching from other paths.

## Implementation

```
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
const dfs = (row, col, index) => {
if (index === word.length) {
return true; // All characters in the word found
}
if (
row < 0 || row >= rows ||
col < 0 || col >= cols ||
board[row][col] !== word[index]
) {
return false; // Out of bounds or character mismatch
}
const temp = board[row][col];
board[row][col] = '#'; // Mark cell as visited
// Explore adjacent cells
const found = (
dfs(row + 1, col, index + 1) ||
dfs(row - 1, col, index + 1) ||
dfs(row, col + 1, index + 1) ||
dfs(row, col - 1, index + 1)
);
board[row][col] = temp; // Backtrack
return found;
};
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (dfs(i, j, 0)) {
return true; // Word found
}
}
}
return false; // Word not found
}
```

## Complexity

– The time complexity of the solution is O(N * M * 4^L), where N and M are the dimensions of the board and L is the length of the word.

– The space complexity is O(L), where L is the length of the word due to the recursive DFS stack.

## Conclusion

In this post, we tackled LeetCode Problem 79 – Word Search using JavaScript. We discussed the problem’s requirements, outlined our approach, and provided a step-by-step solution with code. The DFS strategy allowed us to explore different paths and backtrack when needed. This problem highlights the importance of effective search algorithms in problem-solving. Try experimenting with different test cases to further solidify your understanding. Stay tuned for more LeetCode problem-solving adventures!

For more programming tips, tutorials, and problem-solving solutions, be sure to follow our programming blog. Happy coding!

## Resources

- LeetCode Problem 79 – Word Search
- Visual Algo’s DFS Visualization
- MDN Web Docs JavaScript
- Leetcode Solutions Series click here