Trace a Word Through a Letter Grid

A puzzle magazine prints a grid of letters rows (a list of equal-length strings). A word is hidden if you can spell it by starting on some cell and repeatedly stepping up, down, left or right to a neighbouring cell, never using the same cell twice in one word. Return True if word is hidden in the grid, otherwise False.

Examples

Input:  rows = ["cat", "ore", "wig"], word = "core"
Output: True
Explanation: c(0,0) -> o(1,0) -> r(1,1) -> e(1,2).

Input:  rows = ["cat", "ore", "wig"], word = "cac"
Output: False
Explanation: the only "c" would have to be used twice.

Input:  rows = ["cat", "ore", "wig"], word = "tar"
Output: True

Constraints

• 1 <= len(rows), len(rows[0]) <= 5
• 1 <= len(word) <= 16, lowercase letters

Goals

• Run a depth-first search that marks cells as used and unmarks them on the way back
• Stop as soon as one successful trail is found