The grid board holds one lower-case letter in each cell. You also get a list of distinct words. A word is on the board if you can spell it by tracing a path through the grid: start on any cell, and step each time to a cell directly above, below, left or right of the current one (not diagonally). The cells along the path, in order, must spell the word, and no cell may be used twice in the same path.
Return every word from words that is on the board, each one once, even if several paths spell it. You may return them in any order.
seat runs down from the top-left s to e, right to a and on to t. star is the whole top row. rate starts at its r, goes back to the a, drops to the t below and steps right to e. digs is the bottom row. tea fails: the only e next to a t has no a beside it. stop fails because no o touches a t.
Many paths spell xy, but it is listed once. xyxyx needs five cells and the board has four.
cat is the start of the path that spells cats, and both count. cot would need a t next to the o, and act one next to the c.
Constraints
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j] is a lower-case English letter.1 <= words.length <= 3 × 10⁴1 <= words[i].length <= 10words[i] is made of lower-case English letters.words are different.Searching for each word on its own repeats the same walks again and again. Put all the words in a trie, so that one walk over the board checks every word that starts with the letters walked so far.
One word on its own is Word Search: start from every cell, step to a neighbour whose letter is the next one, and mark the cells on the path so none is used twice. The obvious plan is to run that once per word.
Time O(S + m · n · 3^L)Space O(S)
The full walkthrough and code are part of Premium