Find all dictionary words in a grid

You are given:

• A 2D grid of characters board with m rows and n columns.
• A list of strings words (a dictionary).

A word can be formed by starting from any cell and moving to adjacent cells (up, down, left, right). Each cell may be used at most once in forming a single word.

Return all distinct words from words that can be formed in the grid.

Input

• board : m x n array of lowercase letters.
• words : list of lowercase strings.

Output

• A list (or set) of all dictionary words that appear in the board.

Constraints (reasonable interview constraints)

• 1 <= m, n <= 12
• 1 <= len(words) <= 3 * 10^4
• 1 <= len(word) <= 10
• Letters are lowercase a-z .

Notes

• The interviewer hinted that a trie (prefix tree) is a common approach, but a backtracking solution is also acceptable if performance is addressed.