Word Search II

The problem

You get a board of letters and a list of words. A word is on the board if you can spell it with a path of cells: start at any cell, then keep moving to a cell directly above, below, left or right of the current one, so that the letters you pass spell the word. A cell can be used only once within one word. Return the words that are on the board, each one once even if several paths spell it, in any order. If there are none, return an empty list.

What to write

function solve(board: string[][], words: string[]): string[]

Input
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]

Output
["eat","oath"]

Input
board = [["a","b"],["c","d"]]
words = ["abcb"]

Output
[]

Constraints

Dictionary entries are unique; board dimensions are at most 12 × 12.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The board is small, at most 12 × 12 = 144 cells, so it is the number of words that makes things slow. Searching the whole board once for every word walks the same stretches again and again. Aim to make one walk over the board serve all the words.

2. Hint 2: Ask a smaller question

   Take the words oath and oats. Both start with o, a, t. You are walking the board and have spelled "oat" so far. What do you need to know to decide whether to keep going? Does it matter which of the two words you were looking for?

3. Hint 3: Name the pattern

   Searching for many words at once is the signal for a trie: a tree where each step down is one letter, so words that begin the same share their first steps. Walk the board as in the plain word search, but only while the letters so far form a path in the trie. Read the lesson on trie.

4. Hint 4: State the invariant

   The walk carries a node of the trie, one stop on a path, along with its position on the board. The letters so far are always the path from the top to that node. Keep going only while the next cell's letter is a step down from that node, and never use a cell twice on one path.

5. Hint 5: Sketch the pseudocode

   Build the trie, each word at its last node. From every cell, run walk(cell, root). walk(cell, node): stop if off the board or no child matches the cell's letter. Otherwise record and clear that child's word, if any, mark the cell, walk its four neighbors with the child, unmark the cell, and delete the child if it has no children.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Build a trie of dictionary words and explore board paths only while they match trie prefixes. Remove completed words to avoid duplicates.

The slow way

For each word, run a plain word search: try every cell as the start and follow neighbors that spell the next letter. It is correct, but the board is walked once for every word, and words that begin the same repeat the same walks over the same cells.

The insight

All the words can be searched for at once. Keep them in a trie, a tree with one step per letter in which words that begin the same share their first steps. While you walk the board, the trie tells you which letters can still lead to a word: a path that spells the beginning of no word can be dropped at once.

Step by step

1. Put every word in a trie, keeping the whole word at its last node. Each node is one stop on a path of letters, with a child for each letter that can come next. Words that begin the same share their first nodes; the whole word is kept at its last node.
2. Note the board's size and start an empty list for the words found. The size tells a path when it has walked off the edge of the board. The list collects each word the first time it is found.
3. Stop if the cell is off the board or no word continues with its letter. The trie answers this in one step: does the current node have a child for this letter? If not, no word still to be found begins this way, so no longer path through here can spell one.
4. A node that holds a word is a find: record it and take it out. The path so far spells exactly that word. Taking the word out of the node means that a second path to the same word does not report it again.
5. Mark the cell as used, try its four neighbors, then restore it. A cell can be used once within a word. While marked, the cell holds "#", which no word continues with, so a path that comes back stops there. Restoring the letter afterwards frees the cell for other paths.
6. Remove a node with no children left, so its branch is skipped later. A node with no children has nothing below it: every word at or below it has been found. Removing it makes later paths stop there at once, instead of walking the same dead branch again.
7. Start a path at every cell of the board. A word can begin at any cell. Each start walks from the root of the trie, the node before any letter, so a cell whose letter no word begins with stops at once.

The same numbered steps are the comments in each solution.

function solve(board, words) {
  // 1. Put every word in a trie, keeping the whole word at its last node
  const root = { children: new Map() };
  for (const word of words) {
    let node = root;
    for (const letter of word) {
      if (!node.children.has(letter)) {
        node.children.set(letter, { children: new Map() });
      }
      node = node.children.get(letter);
    }
    node.word = word;
  }

  // 2. Note the board's size and start an empty list for the words found
  const rows = board.length;
  const cols = board[0].length;
  const result = [];

  // 3. Stop if the cell is off the board or no word continues with its letter
  function backtrack(r, c, node) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const letter = board[r][c];
    const child = node.children.get(letter);
    if (child === undefined) return;
    // 4. A node that holds a word is a find: record it and take it out
    if (child.word !== undefined) {
      result.push(child.word);
      delete child.word;
    }
    // 5. Mark the cell as used, try its four neighbors, then restore it
    board[r][c] = "#";
    const neighbors = [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ];
    for (const [nr, nc] of neighbors) {
      backtrack(nr, nc, child);
    }
    board[r][c] = letter;
    // 6. Remove a node with no children left, so its branch is skipped later
    if (child.children.size === 0) {
      node.children.delete(letter);
    }
  }

  // 7. Start a path at every cell of the board
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      backtrack(r, c, root);
    }
  }
  return result;
}

function solve(board: string[][], words: string[]): string[] {
  // A node keeps its children by letter, and the word that ends at it, if any.
  type Node = { word?: string; children: Map<string, Node> };

  // 1. Put every word in a trie, keeping the whole word at its last node
  const root: Node = { children: new Map() };
  for (const word of words) {
    let node = root;
    for (const letter of word) {
      if (!node.children.has(letter)) {
        node.children.set(letter, { children: new Map() });
      }
      node = node.children.get(letter)!;
    }
    node.word = word;
  }

  // 2. Note the board's size and start an empty list for the words found
  const rows = board.length;
  const cols = board[0].length;
  const result: string[] = [];

  // 3. Stop if the cell is off the board or no word continues with its letter
  function backtrack(r: number, c: number, node: Node): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const letter = board[r][c];
    const child = node.children.get(letter);
    if (child === undefined) return;
    // 4. A node that holds a word is a find: record it and take it out
    if (child.word !== undefined) {
      result.push(child.word);
      delete child.word;
    }
    // 5. Mark the cell as used, try its four neighbors, then restore it
    board[r][c] = "#";
    const neighbors = [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ];
    for (const [nr, nc] of neighbors) {
      backtrack(nr, nc, child);
    }
    board[r][c] = letter;
    // 6. Remove a node with no children left, so its branch is skipped later
    if (child.children.size === 0) {
      node.children.delete(letter);
    }
  }

  // 7. Start a path at every cell of the board
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      backtrack(r, c, root);
    }
  }
  return result;
}

def solve(board, words):
    # 1. Put every word in a trie, keeping the whole word at its last node
    root = {"children": {}}
    for word in words:
        node = root
        for letter in word:
            if letter not in node["children"]:
                node["children"][letter] = {"children": {}}
            node = node["children"][letter]
        node["word"] = word

    # 2. Note the board's size and start an empty list for the words found
    rows, cols = len(board), len(board[0])
    result = []

    # 3. Stop if the cell is off the board or no word continues with its letter
    def backtrack(r, c, node):
        if not (0 <= r < rows and 0 <= c < cols):
            return
        letter = board[r][c]
        child = node["children"].get(letter)
        if child is None:
            return
        # 4. A node that holds a word is a find: record it and take it out
        if "word" in child:
            result.append(child.pop("word"))
        # 5. Mark the cell as used, try its four neighbors, then restore it
        board[r][c] = "#"
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            backtrack(nr, nc, child)
        board[r][c] = letter
        # 6. Remove a node with no children left, so its branch is skipped later
        if not child["children"]:
            del node["children"][letter]

    # 7. Start a path at every cell of the board
    for r in range(rows):
        for c in range(cols):
            backtrack(r, c, root)
    return result

Example 1, traced

Input
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]

Output
["eat","oath"]

Why it works

A path is followed only while its letters begin some word of the list, and nodes are removed only when no unfound word passes through them, so no word that is on the board is missed. Following a word's own path from its first cell reaches the node at its end, which reports the word once.

Time and space

Time O(total word length + rows · cols · 4^L), extra space O(total word length + L). Building the trie takes one step per letter of all the words. Paths have at most L cells, L being the longest word's length, and at most 4 choices per step: up to 4^L paths from each of the rows · cols start cells. Space: the trie plus one path.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Restore the cell when its path is done. If it stays marked, later paths cannot use it: in example 1 the only t, on the way to oath, stays blocked, so eat is never found.
• Take a found word out of the trie. Otherwise a word that starts a longer word keeps its node, so a second path reports it again: on the row "a b a" with "ab" and "abc", "ab" comes out twice.
• Remove a node with no children left. Otherwise answers stay right, but dead branches are walked again: on a 6 by 6 board of a's with words of 1 to 12 a's, the search is called 2,502,164 times, not 84.

Pattern

Trie. Builds on Word Search and Implement Trie Prefix Tree.

Keep going