Word Traced on a Letter Grid

Medium

You get an m × n grid of letters grid and a word word. Can you trace the word on the grid? The word is read along a chain of cells: each next cell is horizontally or vertically adjacent to the previous one, and the letters along the chain spell word in order. A cell cannot appear in the chain twice. Case matters: a and A are different letters. Return true if such a chain exists, and false otherwise. How would you prune the search on a larger grid?

Example 1

grid=[["C", "A", "T"], ["O", "R", "S"], ["D", "E", "N"]], word="CARE" → True

C (0,0) → A (0,1) → R (1,1) → E (2,1): each step goes to a horizontally or vertically adjacent cell.

Example 2

grid=[["C", "A", "T"], ["O", "R", "S"], ["D", "E", "N"]], word="CAN" → False

C → A works, but the N sits in the far corner and is not adjacent to the A. The answer is false.

Example 3

grid=[["a", "b"], ["b", "a"]], word="abba" → False

Whichever a you start from, you can step to a b, but its only neighbours hold a, and the other b is diagonal. The answer is false.

Constraints

1 ≤ m, n ≤ 6
1 ≤ len(word) ≤ 15
grid and word consist of lowercase and uppercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Array String Backtracking Matrix

Similar problems

Words Hidden in a Letter Grid Hard Ball Into the Hole Hard Drain the Landlocked Ponds Medium Land Regions on a Map Medium Ratio Chain Queries Medium

Input

grid=[["C", "A", "T"], ["O", "R", "S"], ["D", "E", "N"]], word="CARE"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 20 tests on the server, hidden ones included.