Trace a Word Through Neighboring Grid Cells

### Problem Determine whether the string `query` can be traced through the character grid `letters`. Return a boolean result. Start at any cell. Each next character must come from a cell immediately above, below, to the left, or to the right of the previous cell. Diagonal moves are not permitted. A cell may appear at most once in a trace, and its character must match the corresponding character of `query` exactly. ### Examples **Example 1** ```text Input: letters = [["C","A"],["T","R"]], query = "CAR" Output: true ``` The trace visits the upper-left cell, then the upper-right cell, then the lower-right cell. **Example 2** ```text Input: letters = [["A","B"],["C","D"]], query = "ABA" Output: false ``` Completing this query would require using the only `A` cell again, which is not allowed. ### Constraints - The number of rows and the number of columns are each between `1` and `6`, inclusive. - Every row has the same length. - `1 <= query.length <= 15` - Grid cells and query characters are uppercase or lowercase English letters. ### Optional Follow-up If the grid were larger, how could search pruning reduce the work needed?