Word Search

A grid of letters is given as a list of equal-length strings, one per row. A word can be traced in the grid if you can start on a cell holding its first letter and reach each next letter by stepping to a neighbouring cell (up, down, left or right, not diagonally), never using the same cell twice in one word.

Write word_in_grid(grid, word) that returns True if word can be traced, and False otherwise.

Examples

grid = ["SNAKE",
        "PYTHO",
        "CODEN"]
word_in_grid(grid, "PYTHON")  # returns True
word_in_grid(grid, "CODE")    # returns True
word_in_grid(grid, "NODE")    # returns False

"PYTHON" runs along the middle row and turns down for the N. "NODE" fails: the N in the bottom-right corner touches an O, but no D touches that O, and the other N has no O beside it.

Constraints

• The grid has 1 to 6 rows and 1 to 6 columns.
• 1 <= len(word) <= 15
• All letters are uppercase A to Z.