Trie and Word Search

Opening scenario

Problem references use LC for LeetCode.

Word Search II (LC 212): given an m×n board of letters and a list of words, return every word that can be formed by a path of adjacent (up/down/left/right) cells, no cell reused within a word. The naive approach — run a separate board DFS for each word — is too slow when there are thousands of words. We will first build a Trie with insert, search, and startsWith, then use it to guide the board search. search(word) asks whether that exact word was inserted. startsWith(prefix) asks whether any inserted word begins with it.

Assume a non-empty rectangular board and non-empty words made of lowercase letters. Each matching word appears once in the result, even if several board paths spell it. Start with words such as "oath" and "oat": how much of their board search could they share?