DIY: Word Search II

Problem statement

In this challenge, you will be given a list of strings that you need to find in the 2D grid. Neighboring characters can be combined to form strings. Remember that the diagonals are not included in neighboring characters; only up, down, right, and left neighbors can be considered. The solution should return a list containing the strings from the input list that were successfully found in the grid. To help you solve this problem, you will be provided with an implementation for the Trie class, which you can use to optimize your solution.

Input

The first input will be a 2D list, meaning a list of lists. The 2D list will represent the grid of characters. The second input will be a list of strings that need to be searched in the grid. The following is an example input:

{{'C', 'O', 'L', 'I', 'M'}, 
{'I', 'N', 'L', 'M', 'O'}, 
{'A', 'L', 'I', 'E', 'O'}, 
{'R', 'T', 'A', 'S', 'N'}, 
{'S', 'I', 'T', 'A', 'C'}}

{"REINDEER", "IN", "RAIN"}

Output

The output will be a list of strings containing the strings from the input list found in the grid. The following is an example output for the inputs above:

["IN", "RAIN"]

The order of the strings in the output does not matter.