Trie + board backtracking

Before you start

• Search on a grid

  This combines a trie with grid backtracking: mark a cell, try its neighbors, unmark it. Word Search covers the grid half.

  Open lesson

Why it matters

Boggle solvers and board-based spell checkers may test thousands of dictionary words against the same grid. Running a complete board search per word repeats the same starts and prefixes, making work grow directly with dictionary size. The search must share board work across words and abandon a path that cannot begin any requested word.

A word may be formed by adjacent (4-dir) cells without reuse. Return all words from words that can be formed. Sort the result lexicographically.

Input

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

Output

["oath", "eat"]

On the 4 × 4 board with ["oath", "pea", "eat", "rain"], brute force restarts a board search four times. Follow one trie during the board walk instead, testing all valid dictionary prefixes in one traversal and returning ["oath", "eat"].

Build one trie for ["oath", "pea", "eat", "rain"]. These words share no first letter, but one root still records all four valid starts. From (0, 0), o → a → t → h reaches "oath"; any board prefix absent from the current trie node returns immediately.

Mark each cell "#" while it belongs to the current path, then restore it on return. Starting at e in (1, 3) can follow a at (1, 2) and t at (1, 1) to find "eat". Remove each found word's end mark so another path cannot report it twice.