Word Search on a Letter Grid
Given a grid of lowercase letters and a list of words, return every word that can be traced through four-directionally adjacent cells without reusing a cell. Return the found words sorted, without duplicates.
board = ["oaan",
"etae",
"ihkr",
"iflv"]
findWords(board, ["oath", "pea", "eat", "rain"]) -> ["eat", "oath"]Hints
Hint 1
Searching the board once per word repeats the same walks. Insert all words into a trie, then DFS from every cell following trie children only: a cell whose letter is not a child of the current node ends that branch immediately.
Hint 2
Mark the current cell while exploring its neighbours (a visited set, or a temporary placeholder in a copied grid) and restore it afterwards. Record a word when the node carries an end marker, and add to a set to dedupe.