Word Search II

Problem Statement

Given a 2-D grid of characters board and a list of strings words, return all words that are present in the grid. For a word to be present it must be possible to form the word with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Constraints

• m x n grid of characters where m and n are the number of rows and columns in the grid.
• board[i][j] is a single lowercase or uppercase letter.
• 1 <= words.length <= 3 * 10^4
• 1 <= words[i].length <= 10
• All characters in words[i] are lowercase or uppercase letters.

Examples

Example 1

Input: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Example 2

Input: board = [ ['a','b'], ['c','d'] ] words = ["abcb"]

Output: []

Constraints

• All inputs are composed of lowercase and uppercase letters ('a'-'z', 'A'-'Z').
• The number of words is at most 2000.
• The number of characters in each word is at most 2000.
• It is guaranteed that all characters in the grid and words are consistent with the ASCII table.

Hints

• Use backtracking to solve this problem.
• Try to optimize the search by using a Trie to store the words and then search for prefixes in the Trie while traversing the board.