Word Search II

Problem Given an m × n board of letters and a list of words, return all words from the list that can be formed by a sequence of adjacent (horizontally or vertically neighbouring) cells, where each cell is used at most once within a single word.

Input / Output

• Input: char grid board, list of strings words.
• Output: every word from words that appears in the grid.

Constraints

• Up to 10^4 words.
• A cell may not be reused within one word.

Example

• board = [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]], words = ["oath","pea","eat","rain"] → ["oath","eat"].