Solving Word Search in JavaScript: Step-by-Step Guide

Solving Word Search in JavaScript: Step-by-Step Guide

The Word Search problem is one of the most popular algorithmic challenges you will encounter in coding interviews and competitive programming. Given a two-dimensional grid of characters and a target word, your task is to determine whether the 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 in a single construction.

What Is the Word Search Problem?

Formally, you are given an m x n matrix of characters and a string word. You must return true if the word exists in the grid, otherwise false. The letters of the word must be formed by traversing adjacent cells in one of four directions: up, down, left, or right. Diagonal movement is not allowed, and you cannot revisit a cell within the same search path.

This problem is a classic application of Depth-First Search (DFS) combined with backtracking. The DFS explores each possible path from a starting cell, and backtracking ensures that once a path is proven invalid, the algorithm reverts its state and tries another direction.

Why It Matters

• Interview relevance: It tests your understanding of recursion, backtracking, and matrix traversal — all fundamental concepts.
• Real-world applications: Similar algorithms power puzzle games, OCR post-processing, DNA sequence matching, and pathfinding systems.
• Algorithmic foundation: Mastering this problem prepares you for more complex graph and grid problems like N-Queens, Sudoku Solver, and Rat in a Maze.
• State management practice: It teaches you how to carefully mark and unmark visited cells, a pattern reused across many backtracking problems.

Understanding the Approach

The strategy breaks down into two phases. First, scan the grid to find every cell whose character matches the first letter of the target word. Each of these cells is a potential starting point. Second, from each starting point, perform a DFS that attempts to match the remaining characters of the word by moving to valid adjacent cells.

During the DFS, you must mark the current cell as visited to prevent reuse. A common and efficient technique is to temporarily overwrite the cell's value with a sentinel character (such as #) and restore it after the recursive calls complete. This avoids the overhead of maintaining a separate visited matrix.

Step-by-Step Implementation

Let us build the solution incrementally. First, we define the main function that iterates over the grid and triggers the DFS whenever the first character matches.

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

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === word[0] && dfs(board, word, r, c, 0)) {
        return true;
      }
    }
  }
  return false;
}

Next, we implement the recursive DFS function. It checks whether the current cell matches the expected character, marks it as visited, and recursively explores all four directions. If any direction returns true, the word has been found.

function dfs(board, word, r, c, index) {
  // Base case: all characters matched
  if (index === word.length) {
    return true;
  }

  // Boundary and character checks
  if (
    r < 0 || r >= board.length ||
    c < 0 || c >= board[0].length ||
    board[r][c] !== word[index]
  ) {
    return false;
  }

  // Mark the cell as visited by temporarily changing its value
  const temp = board[r][c];
  board[r][c] = '#';

  // Explore all four directions
  const found =
    dfs(board, word, r + 1, c, index + 1) ||
    dfs(board, word, r - 1, c, index + 1) ||
    dfs(board, word, r, c + 1, index + 1) ||
    dfs(board, word, r, c - 1, index + 1);

  // Restore the original value (backtracking)
  board[r][c] = temp;

  return found;
}

Now let us combine everything into a single, self-contained module and test it with a sample grid.

const board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
];

console.log(exist(board, 'ABCCED')); // true
console.log(exist(board, 'SEE'));    // true
console.log(exist(board, 'ABCB'));   // false

In the first example, the path A → B → C → C → E → D traces a valid route through the grid. The second example finds S → E → E starting from the rightmost column. The third example fails because revisiting the same B cell would be required, which the algorithm correctly prevents.

Complexity Analysis

Let m be the number of rows, n the number of columns, and L the length of the target word. In the worst case, the algorithm starts a DFS from every cell, and each DFS can branch into four directions up to L times. This yields a time complexity of O(m × n × 4^L). The space complexity is O(L) due to the recursion stack, since we mark visited cells in place rather than allocating an auxiliary structure.

Best Practices and Optimizations

• Reverse the word when beneficial: If the last character of the word appears fewer times in the grid than the first character, search the reversed word instead. This prunes many invalid paths early.
• Count characters first: If the grid does not contain enough of a particular character required by the word, return false immediately without running any DFS.
• Avoid spreading arrays in recursion: Mutating the board in place and restoring values is significantly faster than cloning visited sets or boards on every recursive call.
• Use iterative DFS for very large grids: If stack overflow is a concern, convert the recursion into an explicit stack-based approach.
• Early termination: Return as soon as a valid path is found rather than continuing to explore the rest of the grid.

Here is an optimized version that includes character frequency pre-checking and word reversal based on rarity.

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

  // Count character frequencies in the board
  const count = {};
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const ch = board[r][c];
      count[ch] = (count[ch] || 0) + 1;
    }
  }

  // Reverse the word if the last character is rarer than the first
  if ((count[word[0]] || 0) > (count[word[word.length - 1]] || 0)) {
    word = word.split('').reverse().join('');
  }

  // Early exit if any required character is insufficient
  for (const ch of word) {
    if (!count[ch]) return false;
    count[ch]--;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === word[0] && dfs(board, word, r, c, 0)) {
        return true;
      }
    }
  }
  return false;
}

Common Pitfalls to Avoid

• Forgetting to restore the cell value: If you mark a cell as visited but never restore it, subsequent searches from other starting points will see a corrupted board.
• Checking boundaries after accessing the cell: Always validate row and column indices before reading board[r][c] to avoid runtime errors.
• Using diagonal moves: The problem restricts movement to four directions. Including diagonals will produce incorrect results.
• Revisiting cells: Without proper marking, the algorithm can loop infinitely between two adjacent matching cells.

Extending to Multiple Words

A natural extension is Word Search II, where you must find all words from a given list that exist in the grid. While you could run the single-word solution for each entry, this becomes inefficient for large word lists. The preferred approach uses a Trie data structure to share prefixes across words, allowing a single DFS pass to match many words simultaneously.

class TrieNode {
  constructor() {
    this.children = {};
    this.word = null;
  }
}

function buildTrie(words) {
  const root = new TrieNode();
  for (const word of words) {
    let node = root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.word = word;
  }
  return root;
}

function findWords(board, words) {
  const root = buildTrie(words);
  const result = [];
  const rows = board.length;
  const cols = board[0].length;

  function dfs(r, c, node) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const ch = board[r][c];
    if (!node.children[ch]) return;

    const next = node.children[ch];
    if (next.word) {
      result.push(next.word);
      next.word = null; // avoid duplicates
    }

    board[r][c] = '#';
    dfs(r + 1, c, next);
    dfs(r - 1, c, next);
    dfs(r, c + 1, next);
    dfs(r, c - 1, next);
    board[r][c] = ch;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      dfs(r, c, root);
    }
  }
  return result;
}

This Trie-based approach dramatically reduces redundant work when many words share common prefixes, making it the standard solution for the multi-word variant.

Solving the Word Search problem in JavaScript is an excellent way to deepen your understanding of backtracking and grid traversal. By combining a careful scan for starting points, an in-place visited marker, and disciplined boundary checks, you can build a correct and efficient solution. The optimizations around character frequency and word reversal further demonstrate how small analytical improvements can yield meaningful performance gains, while the Trie extension shows how the same foundational ideas scale to more demanding variants of the problem.