Word Search II: Trie + Backtracking on Grid

Word Search II (LeetCode 212): given an m × n board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (horizontally or vertically), where each cell can only be used once. This is harder than Word Search I (single word) because we need to find all matching words simultaneously — naively running Word Search I for each word is O(W × m × n × 4^L) which is too slow.

Inserting all target words into a trie and then running DFS backtracking on the board allows us to search for all words simultaneously. At each board cell, instead of checking 'does this path spell my target word?', we check 'does this path match a prefix in the trie?'. As soon as a trie prefix fails, we prune the entire DFS branch — avoiding redundant work across all words sharing that prefix.