Word Search With Backtracking

A Bloomberg Terminal component receives a grid of lowercase characters and a dictionary of candidate labels. Return every dictionary word that can be formed by starting at any cell and moving up, down, left, or right. A cell may not be used more than once for the same word.

Implement find_words(board, words) and return the discovered words in lexicographic order without duplicates. The solution should use a trie to share prefix work across words and backtracking to explore valid paths.

Formal Specification

• board is a non-empty rectangular list of lists of one-character strings.
• words is a list of non-empty lowercase strings.
• Return a list of distinct words from words that can be constructed in board.
• Movement is limited to the four orthogonal directions. Diagonal movement is not allowed.
• The input board may be modified temporarily during searching, but must be restored before the function returns.

Examples

Example 1

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']

eat and oath have valid paths. pea and rain do not.

Example 2

board = [['a','b'], ['c','d']], words = ['ab', 'abcd', 'aba']

Output: ['ab', 'abcd']

abcd can use all four cells, while aba would need to reuse the first cell.

Constraints

• 1 <= rows, columns <= 12
• 1 <= len(words) <= 30,000
• 1 <= len(word) <= 20
• All board characters and word characters are lowercase English letters.