Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Given an m x n board of characters and a list of words, return all words on the board.
Example
Input: board = [["o","a","a","n"],
["e","t","a","e"],
["i","h","k","r"],
["i","f","l","v"]], words = ["oath","oathes","pea","eat","rain"]
Output: ["eat","oath","oathes"]This problem is a classic board-search variant: find all dictionary words that can be formed by moving horizontally or vertically through adjacent cells without reusing the same cell in one word. The efficient solution combines a Trie to store the word list with DFS backtracking on the board, using prefix pruning to cut off impossible paths early. In the example, the board contains eat, oath, and oathes, so the algorithm must support both exact matches and longer words that share prefixes.
