Word Search II

Problem Given an m x n board of characters and an array of strings words, return all words that can be found in the board. A word is formed from sequentially adjacent cells (up/down/left/right). The same cell may not be used more than once in a single word. Input First line: m n Next m lines: a string of length n representing the board Next line: integer k (#words) Next k lines: one word per line Output Print all found words, one per line, in any order. Constraints 1 <= m, n <= 12 1 <= k <= 3 * 10^4 1 <= word.length <= 10 All words are unique Example Input 4 4 oaan etae ihkr iflv 4 oath pea eat rain Output oath eat