Word Search II

You are given an m × n grid of lowercase letters board and a list of distinct words words.

A word is on the board if you can spell it by starting at some cell and repeatedly stepping to a cell that shares a side with the current one (up, down, left or right), reading one letter per cell. A single cell may be used at most once within the same word, although different words may reuse the same cells.

Return every word from words that is on the board. Each found word should appear once, and the result may be in any order.

Example 1

Example 2

Example 3

Constraints

• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 × 104
• 1 <= words[i].length <= 10
• All words are distinct and consist of lowercase letters.

Pattern Path · Backtracking · problem 125 of 169

Start simple

Run a separate backtracking search for every word: O(W · m · n · 3^L) for W words of length L, which repeats shared prefixes many times.

The key idea

A single word can be found with backtracking from every cell. The cost comes from repeating that for thousands of words, many of which share prefixes. Instead, search for all words together, guided by a trie built from the word list.

Start a DFS from every cell whose letter is a child of the trie root. Each step on the board moves one level deeper in the trie, so at any moment the trie node tells you which letters could continue a real word. If the neighbouring cell's letter is not a child of the current node, that direction is abandoned immediately: no word starts with that prefix. Mark a cell while it is on the current path and restore it when backtracking, so a word never reuses a cell.

Two refinements make it fast in practice. Store the complete word in its end node, and remove it once reported, so duplicates are impossible and no string building is needed. And after exploring a node, delete it from its parent if it has no children left: once every word under a prefix has been found, later starting cells will not waste time exploring it.

The worst case is still exponential in the word length L (at most 3 new directions per step), but each board path is walked once for all words at the same time.

Complexity

• Time: O(m &middot; n &middot; 3<sup>L</sup>) for the search plus O(total letters) to build the trie
• Space: O(total letters in words)

Python

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # Build a trie of nested dicts; the key "$" marks a complete word.
        trie = {}
        for word in words:
            node = trie
            for ch in word:
                node = node.setdefault(ch, {})
            node["$"] = word

        rows, cols = len(board), len(board[0])
        found = []

        def dfs(r, c, parent):
            ch = board[r][c]
            node = parent[ch]
            if "$" in node:
                found.append(node.pop("$"))  # pop so each word is reported once
            board[r][c] = "#"                # mark the cell as used on this path
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in node:
                    dfs(nr, nc, node)
            board[r][c] = ch                 # undo the mark when backtracking
            if not node:
                del parent[ch]               # prune: nothing left to find below

        for r in range(rows):
            for c in range(cols):
                if board[r][c] in trie:
                    dfs(r, c, trie)
        return found

JavaScript

var findWords = function(board, words) {
  // Build a trie of nested Maps; the key "$" marks a complete word.
  const trie = new Map();
  for (const word of words) {
    let node = trie;
    for (const ch of word) {
      if (!node.has(ch)) node.set(ch, new Map());
      node = node.get(ch);
    }
    node.set("$", word);
  }

  const rows = board.length, cols = board[0].length;
  const found = [];

  const dfs = (r, c, parent) => {
    const ch = board[r][c];
    const node = parent.get(ch);
    if (node.has("$")) {
      found.push(node.get("$"));
      node.delete("$"); // delete so each word is reported once
    }
    board[r][c] = "#";  // mark the cell as used on this path
    for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && node.has(board[nr][nc])) {
        dfs(nr, nc, node);
      }
    }
    board[r][c] = ch;   // undo the mark when backtracking
    if (node.size === 0) parent.delete(ch); // prune: nothing left to find below
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (trie.has(board[r][c])) dfs(r, c, trie);
    }
  }
  return found;
};

What the interviewer is checking

The interviewer wants to see you combine two tools: backtracking on a grid and a trie for prefix pruning, and then tighten it with pruning of finished branches.

Mistakes to avoid

• Reporting the same word twice when it can be traced along two different paths.
• Forgetting to restore a cell after backtracking, which hides it from later paths.
• Stopping the search when a word is found, even though a longer word may continue from the same node (app and apple).
• Rebuilding prefix strings and looking them up in a set at every step, which is slow.

Follow-ups to expect

• What if the board is fixed and many word lists arrive? (Pre-index board paths, or cache per prefix.)
• Allow diagonal moves. (Eight neighbours; same trie pruning.)
• Return the paths of the found words. (Record coordinates on the DFS stack.)

In real software

Word games like Boggle solvers, autocomplete over a keyboard swipe path, and multi-pattern search in DNA grids or images all walk a structure while descending a trie of candidate patterns.

Practice next