Trace a Word on the Board

MediumBacktracking

Problem

A letter board is given as board, an array of equal-length strings (one string per row). You may trace a word by starting on any cell and repeatedly moving to a cell that shares a side (up, down, left, right). A cell may be used at most once in one trace.

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

Example 1

Input:
board = ["ABCE", "SFCS", "ADEE"], word = "ABCCED"
Output:
true

A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1).

Example 2

Input:
board = ["ABCE", "SFCS", "ADEE"], word = "ABCB"
Output:
false

The only B would have to be reused.

Constraints

  • 1 ≤ rows, cols ≤ 6
  • 1 ≤ word.length ≤ 15
  • board and word contain only uppercase English letters.

Hint

Show the first hint

Try every cell as the starting point of the trace.

Walkthrough

How to approach it

01Clarify before coding

  • Are diagonal moves allowed? No, only the four side neighbours.
  • Can a cell be reused in the same trace? No.
  • Is the board ragged? No, all rows have the same length.

02Brute force

Enumerate every simple path on the grid and compare its letters to word.

Cost: The number of simple paths is exponential in the number of cells (rows · cols up to 36), so this explodes long before reaching the word length.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.