Trace a pattern through a grid of tiles

Question

You have a grid of single-character tiles. Decide whether a target pattern can be traced as a path of orthogonally adjacent tiles (up/down/left/right), where each tile is used at most once per path.

grid = [["A","B","C"],
        ["S","F","D"],
        ["A","D","E"]]
pattern = "ABFDE"  ->  True     # (0,0)->(0,1)->(1,1)->(2,1)->(2,2)

Return whether the pattern exists as a non-self-intersecting path in the grid.

Accepted Answer

From every cell whose letter matches the first character, run a depth-first search that matches the next character in each of the four directions. Mark a cell as visited by temporarily overwriting it (a sentinel), recurse, then restore it on the way back so other search branches can still use it. Success is reaching the end of the pattern. For the example, the path A - B - F - D - E walks right, right, down, down and matches, so the answer is True. Time O(rows cols 4^L) worst case for a pattern of length L, space O(L) recursion depth. Edge cases: an empty pattern is trivially present; the in-…

Trace a pattern through a grid of tiles

Your answer

More Coding questions