DIY: Word Search II

Problem statement

In this challenge, you will be given an array 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 an array containing the strings from the input array 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 array, meaning an array of arrays. The 2D array will represent the grid of characters. The second input will be an array 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 an array of strings containing the strings from the input array 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.

Coding exercise

You need to implement the findStrings(grid, strings) function, where the grid is a 2D array of characters and strings is the array of strings that we are searching for. The function returns an array of strings representing the strings that were found.