Skip to content
RED SAGSkills
medium30 ptsbacktrackingmatrixdfs

Trace a Word on a Letter Board

A letter board is given as an array of equal-length strings board, one string per row. You can trace a word by starting on any cell and repeatedly stepping to a cell directly above, below, left or right. A cell may be used at most once in a trace.

Return true if word can be traced on the board, otherwise false.

Example 1

Input: board = ["CATS","ROPE","ENDS"], word = "CROP"
Output: true
Explanation: C(0,0) → R(1,0) → O(1,1) → P(1,2).

Example 2

Input: board = ["CATS","ROPE","ENDS"], word = "OPEN"
Output: false
Explanation: After O-P-E there is no N next to the E.

Constraints

  • 1 <= rows, cols <= 6
  • 1 <= word.length <= 15
  • Board and word contain uppercase letters only.
Hint 1

Try every cell as a start and extend the trace with depth-first search.

Hint 2

Mark a cell as used while it is on the current path and unmark it when you backtrack.

Hint 3

Quick rejections help: check letter counts first, and start from whichever end of the word is rarer on the board.

Discussion 0

Join free to post in the discussion.

Good practice for: Game Developer, Frontend Developer, Mobile App Developer, Full Stack Developer, Automation Test Engineer

Run checks your code on 3 sample tests. Submit runs all 10 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.