Find Words in Grid

You're given a grid of single-letter cells and a dictionary of words. Return every dictionary word that can be spelled by walking from cell to adjacent cell, never stepping on the same cell twice within one word. This is the core of Boggle — the word game where you race to find words on a tray of lettered dice — and the same shape powers word-search solvers and "find words on a board" autocomplete features.

Signature

// grid: string[][]
//   A rectangular grid. Each cell is a single, lowercase character.
//   grid[r][c] is the letter at row r, column c. All rows have equal length.
// words: string[]
//   The dictionary to search for. May contain duplicates.
// returns: string[]
//   The subset of `words` that can be traced on the grid, with duplicates
//   removed, sorted ascending (lexicographically).
function gridFindWords(grid, words): string[];

A word can be formed if there is a path c0, c1, c2, … of grid cells where grid[c0] is the word's first letter, grid[c1] its second, and so on, each consecutive pair of cells is adjacent, and no cell repeats within that single path.

Examples

// "cat" runs left-to-right on row 0; "dog" runs left-to-right on row 1.
// "fox" has no matching path, so it is dropped. Output is sorted.
const grid = [
  ['c', 'a', 't'],
  ['d', 'o', 'g'],
];
gridFindWords(grid, ['dog', 'cat', 'fox']); // → ['cat', 'dog']

// 'a' sits at (0,0) and 'b' at (1,1) — they touch only on the diagonal.
// 8-directional adjacency includes diagonals, so "ab" is found.
const grid = [
  ['a', 'x'],
  ['x', 'b'],
];
gridFindWords(grid, ['ab']); // → ['ab']

// Only one 'o' cell. Spelling "oo" would need to step on it twice — not
// allowed — so "oo" is not found. "ot" is found (o then t, adjacent).
const grid = [
  ['o', 't'],
  ['x', 'y'],
];
gridFindWords(grid, ['oo', 'ot']); // → ['ot']

Notes

• Adjacency is 8-directional. From a cell, you may step to any of its (up to) eight neighbours: horizontal, vertical, and diagonal. This is classic Boggle. (Some variants use 4-directional; this one does not.)
• No cell reuse within a word. A single word's path may visit each cell at most once. The grid resets fresh for the next word — reuse is only forbidden inside one word's path.
• The grid is rectangular. Every row has the same length. Cells are single, lowercase characters.
• Output is deduped and sorted. If the dictionary lists "cat" twice, the result contains "cat" once. The same word found via two different paths is also returned once. Sort the result ascending.
• Don't worry about uppercase letters, multi-character cells, non-rectangular grids, or returning the path — you only return which words are formable.