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.

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Approach to solving word search problem:

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

1. We’ll iterate through each cell of the board and start a depth-first search (DFS) for the target word.
2. If the current cell’s character matches the first letter of the word, we’ll start the DFS from that cell.
3. During the DFS, we’ll check adjacent cells for the next character in the word.
4. 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