Find Dictionary Words in a Letter Board

# Find Dictionary Words in a Letter Board Given a rectangular lowercase-letter `board` and a list of distinct `words`, return every listed word that can be formed on the board. A word follows a sequence of horizontally or vertically adjacent cells. A cell may appear at most once in the path for one word. Different words may use the same board cells. Return each found word once, in any order. ### Function `vector<string> findWords(vector<vector<char>>& board, vector<string>& words)` ### Example 1 ```text board = [["c","a","t"],["r","r","e"]] words = ["cat","car","care","tar","tea","acre"] Output: ["care","cat","tar","car"] ``` One path for `"care"` is `(0,0) -> (0,1) -> (1,1) -> (1,2)`. The word `"tea"` cannot be completed after moving from `t` to `e`. Another order of the same four output words is equally valid. ### Example 2 ```text board = [["a","b"],["c","d"]] words = ["aba","ad","bd","ac"] Output: ["ac","bd"] ``` `"aba"` would need to reuse its starting cell. `"ad"` requires a diagonal move. Neither is allowed. ### Constraints - `1 <= board.length, board[i].length <= 12`. - The board is rectangular, and each cell is a lowercase English letter. - `1 <= words.length <= 30000`. - `1 <= words[i].length <= 10`. - Each word consists of lowercase English letters, and all input words are distinct. ### Clarifications Coordinates in the explanations are zero-based. Finding a word through several different paths still contributes only one copy of that word to the result. A path may turn, but it may not leave the board or reuse a cell within that path. ### What a Strong Answer Covers - How to enforce orthogonal movement and the per-path cell-use restriction. - Why the returned set contains every valid input word and no invalid or repeated word. - How work can be shared across a large dictionary without changing the required result. - Search costs using both the board size and the maximum input-word length.