Word Search II

Given a grid of lowercase letters and a dictionary words, return every distinct word that can be formed by walking horizontally or vertically adjacent cells. A board cell may be used at most once per word.

To keep judge output deterministic, return the found words sorted in ascending lexicographic order.

Input / output

• Input: board: string[], words: string[]
• Output: string[] sorted ascending, with no duplicates

Examples

1. board = ["oaan","etae","ihkr","iflv"], words = ["oath","pea","eat","rain"] returns ["eat","oath"].
2. board = ["ab","cd"], words = ["abcb","ab","abc","abd"] returns ["ab","abd"].
3. board = ["a"], words = ["a","aa","b"] returns ["a"].

Constraints

• 1 <= board.length, board[i].length <= 12
• 1 <= words.length <= 3000
• 1 <= words[i].length <= 10
• Board rows and words contain lowercase English letters
• words may contain duplicates, but the output should list each found word once

Target complexity

• Aim for a trie-backed search that shares prefixes, rather than running a full DFS independently for every word.

Hints

1. Solving ordinary Word Search separately for each candidate word repeats the same prefix work again and again.
2. Insert all words into a trie, then walk the board once while pruning any path that no longer matches a trie prefix.

Follow-up How would you remove found words from the trie aggressively so later DFS branches prune even earlier?