Trie Word Search on Grid

Meta wants to scan a character grid for valid keywords that may appear in surfaces like Messenger game boards. Given a 2D board of lowercase letters and a list of lowercase words, return all words that can be formed by traversing adjacent cells.

A word can be constructed from letters of sequentially adjacent cells, where adjacency is horizontal or vertical. The same cell may not be used more than once in a single word.

Formal Specification

Implement a function that takes:

• board: a list of m rows, each row a list of n lowercase characters
• words: a list of distinct lowercase strings

Return a list of all words from words that appear in the board. The output may be in any order.