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

Solving LeetCode Problem 79 – Word Search in JavaScript