Blind 75 · Tries
Same board as Word Search — rows of equal-length strings, steps to horizontally or vertically adjacent cells, no cell reused within one word's trace — but now a whole list of words.
Return the words from the list that can be traced on the board, in alphabetical order, each at most once.
Example 1: Input: board = ["oaan","etae","ihkr","iflv"], words = ["oath","pea","eat","rain"] Output: ["eat","oath"] Example 2: Input: board = ["ab","cd"], words = ["ab","acb","abdc","abcd"] Output: ["ab","abdc"] Example 3: Input: board = ["a"], words = ["a","aa"] Output: ["a"] Example 4: Input: board = ["aaa","aaa","aaa"], words = ["aaaaaaaaa","aaaaaaaaaa"] Output: ["aaaaaaaaa"] Explanation: nine a's can snake through every cell once; a tenth needs a reuse.
1 <= rows, columns <= 12 1 <= words.length <= 100 1 <= words[i].length <= 10 Board and words consist of lowercase English letters; words are distinct.
Backtracking — choose, recurse, undo. The undo is what makes the rest correct.
Pruning: cutting a branch the moment it cannot lead anywhere.
Run the single-word search once per word. At these board sizes it passes, and it is the answer to give before the clever one — an interviewer wants the working version on the board before the optimisation.
1. For each word, run the Word Search DFS.
2. Collect the ones that trace.
3. Sort the results.
Time O(words x cells x 3^len). Space O(len).
Searching per word re-walks the board for every word, and words sharing a prefix re-walk the same cells. Put the words in a trie and walk the board ONCE, descending the trie as the path grows: shared prefixes are explored a single time, and a path dies the moment the trie has no child for the next letter — which is the pruning that makes a large word list tractable.
1. Insert every word into a trie, marking ends.
2. DFS from each cell, carrying the matching trie node.
3. A node marking a word end records that word.
4. Mark and unmark cells as in Word Search.
Time O(cells x 3^maxLen) for the single walk, independent of the number of words. Space O(total letters) for the trie.