Day 6 - Challenge 2 - Search a word in 2D grid of letters

Solving the Word Search Problem using JavaScript

Introduction: 

The Word Search problem is a classic puzzle where you're given a grid of letters and a target word, and you need to determine whether the word can be formed by tracing adjacent cells in the grid. In this blog post, we'll explore how to solve the Word Search problem using JavaScript. We'll cover the algorithmic approach, provide a step-by-step guide to implementation, and discuss some optimizations to make our solution more efficient.

Algorithmic Approach: 

To solve the Word Search problem, we can employ a Depth-First Search (DFS) approach. We'll traverse the grid and recursively check adjacent cells to see if the current cell matches the next letter of the target word. If it does, we continue the search from that cell. We need to keep track of the cells we've already visited to avoid revisiting them and getting stuck in an infinite loop.

Implementation Steps: 

Let's break down the implementation into steps:

1. Define a function called exist that takes the grid, target word, and grid dimensions as parameters.
2. Create a nested loop to iterate through each cell in the grid.
3. For each cell, call a helper function (e.g., search) that performs the DFS search for the target word.
4. Inside the search function, check if the current cell matches the first letter of the target word.
5. If the letter matches, mark the cell as visited and recursively search its adjacent cells for the next letter.
6. If the target word is found, return true. Otherwise, backtrack by marking the cell as unvisited and returning false.
7. Repeat steps 3-6 for each adjacent cell (up, down, left, and right).
8. If no solution is found, return false from the exist function.

Code Implementation: 

Here's a skeleton implementation of the Word Search problem in JavaScript:

function exist(board, word) {
    const rows = board.length;
    const cols = board[0].length;

    function search(row, col, index) {
        if (index === word.length) {
            return true; // Word found
        }

        if (
            row < 0 || row >= rows ||
            col < 0 || col >= cols ||
            board[row][col] !== word[index]
        ) {
            return false; // Out of bounds or mismatch
        }

        const originalChar = board[row][col];
        board[row][col] = '#'; // Mark cell as visited

        // Search in all four directions
        const found =
            search(row + 1, col, index + 1) ||
            search(row - 1, col, index + 1) ||
            search(row, col + 1, index + 1) ||
            search(row, col - 1, index + 1);

        board[row][col] = originalChar; // Revert cell to original

        return found;
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (search(i, j, 0)) {
                return true;
            }
        }
    }

    return false; // Word not found
}

// Example usage
const board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
];
const word = "ABCCED";
console.log(exist(board, word)); // Output: true

Conclusion: 

In this blog post, we've explored the Word Search problem and implemented a solution using JavaScript. We've seen how the Depth-First Search approach can be used to navigate through the grid and find the target word. By understanding the algorithmic approach and following the step-by-step implementation guide, you can solve the Word Search problem and enhance your problem-solving skills in JavaScript.

 

Now write the same program in your favorite language in comment section. 

Other Challenges:

1. Day 3 Challenges
2. Day 4 Challenges
3. Day 5 Challenges