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

Word Search II is a classic algorithmic problem that combines two fundamental computer science concepts: tries (prefix trees) and backtracking depth-first search. It is a popular interview question because it tests your ability to optimize a naive solution using the right data structure. In this tutorial, we will break down the problem, build the solution incrementally, and discuss best practices for writing clean, efficient JavaScript code.

What Is Word Search II?

The problem statement is straightforward. You are given:

A 2D grid (board) of characters.
An array of words (strings).

Your task is to return all words from the array that can be found in the grid. A word can be constructed by traversing sequentially adjacent cells, where "adjacent" means horizontally or vertically neighboring. The same cell may not be used more than once in a single word's construction.

For example, given the board:

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

and the words ["oath","pea","eat","rain"], the output should be ["oath","eat"].

Why It Matters

The naive approach — searching for each word independently using DFS — has a time complexity of O(N * M * 4^L) per word, where N and M are the board dimensions and L is the word length. When you have many words, this becomes extremely slow because you repeatedly explore the same paths.

A trie solves this by sharing common prefixes. Instead of searching for each word separately, you search the entire board once, walking down the trie as you go. This dramatically reduces redundant work and is a perfect example of how choosing the right data structure transforms an algorithm's performance.

Building the Trie

First, we need a trie to store all the words. Each node will have a map of children characters and an optional flag (or value) indicating that a complete word ends at this node.

class TrieNode {
  constructor() {
    this.children = {};
    this.word = null; // stores the complete word at the terminal node
  }
}

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; // mark the end of a word
  }
  return root;
}

Storing the full word at the terminal node is a small but powerful trick. When we reach a node where word is not null, we know we have found a valid word, and we can push it directly to our results array without reconstructing it from the path.

Implementing the Backtracking DFS

Now we traverse every cell in the board. For each cell, if its character matches a child of the trie root, we begin a DFS. During the DFS, we mark the current cell as visited (by temporarily changing its value) and explore all four directions.

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

  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
  ];

  function dfs(r, c, node) {
    const ch = board[r][c];

    // If this character is not in the trie path, stop.
    if (!node.children[ch]) return;

    const nextNode = node.children[ch];

    // If we reached a complete word, record it.
    if (nextNode.word !== null) {
      result.push(nextNode.word);
      nextNode.word = null; // avoid duplicate entries
    }

    // Mark the cell as visited.
    board[r][c] = '#';

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
        dfs(nr, nc, nextNode);
      }
    }

    // Restore the cell after backtracking.
    board[r][c] = ch;

    // Optional optimization: prune leaf nodes.
    if (Object.keys(nextNode.children).length === 0) {
      delete node.children[ch];
    }
  }

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

  return result;
}

How the Algorithm Works Step by Step

Let us trace through the logic to make sure each piece is clear:

Build the trie: All input words are inserted into a shared trie. This is done once, in O(total characters across all words) time.
Iterate the board: For every cell, we attempt to start a DFS from the trie root.
DFS traversal: If the current cell's character exists as a child of the current trie node, we move deeper. Otherwise, we return immediately — this pruning is what makes the trie so efficient.
Record words: Whenever we land on a trie node that has a non-null word property, we add that word to the results and set word to null to prevent duplicates.
Backtrack: After exploring all four directions, we restore the cell's original character so other paths can use it.
Prune leaves: If a trie node has no children left after exploration, we delete it from its parent. This prevents revisiting dead branches from other starting cells.

Testing the Solution

Here is a complete, runnable example you can paste into a Node.js environment:

const board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
];

const words = ["oath","pea","eat","rain"];

console.log(findWords(board, words));
// Output: [ 'oath', 'eat' ]

You can also test edge cases such as an empty board, an empty word list, or words that share prefixes like ["app", "apple", "apply"] to confirm the trie correctly handles overlapping paths.

Complexity Analysis

Let N be the number of rows, M the number of columns, and L the maximum length of any word. The worst-case time complexity is O(N * M * 4^L), which occurs when every cell can start a path exploring all four directions up to depth L. In practice, the trie prunes most branches early, so the average case is far better than the naive per-word approach.

Space complexity is O(total characters in all words) for the trie, plus O(L) for the recursion stack during DFS.

Best Practices

Use a class for TrieNode: It keeps the code readable and makes it easy to extend the node with additional metadata if needed.
Mark visited cells in place: Temporarily replacing the cell value with a sentinel like '#' avoids allocating a separate visited matrix and keeps memory usage low.
Prune the trie: Deleting leaf nodes after they are fully explored prevents redundant traversals and is one of the most impactful optimizations in this problem.
Avoid duplicates: Setting node.word = null after collecting a word ensures each word appears only once in the output, even if it can be formed by multiple paths.
Validate inputs: Always check for empty boards or empty word arrays before running the main logic to avoid runtime errors.
Prefer iterative trie building: Building the trie with simple loops is both fast and easy to debug compared to recursive insertion.

Common Pitfalls

One frequent mistake is forgetting to restore the board cell after the recursive calls. Without restoration, subsequent paths from other starting cells will see corrupted board state and miss valid words. Another common issue is pushing the same word multiple times when multiple paths form it — the null-out trick above solves this cleanly.

Developers also sometimes try to reconstruct the word by concatenating characters along the DFS path. While this works, it is slower and more error-prone than simply storing the complete word at the terminal trie node and reading it directly.

Conclusion

Word Search II is a powerful demonstration of how combining a trie with backtracking DFS can turn an expensive brute-force search into an elegant, efficient solution. By sharing prefixes across all words, pruning dead branches, and marking visited cells in place, you get an algorithm that performs well even on large boards with many words. Mastering this pattern will not only help you ace interviews but also deepen your understanding of when and why to reach for a trie in real-world problems involving prefix matching, autocomplete, and dictionary lookups.