Show problems as
Classic problem #79MediumArrayStringBacktrackingDepth-First SearchMatrix

Word Search

Real-world version: Tablet Glyph Trail
Tracked in this browser only
Read Word Search on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstBacktracking · Recursion, animated step by step

A conservation lab photographs a stone tablet as a grid tablet of glyph marks, one mark per square: tablet[r][c] is a one-character string.

A restorer wants to know whether the inscription mark_run was cut into the stone as a single continuous trail. A trail begins on any square, and from the square it currently occupies it moves to a square sharing a side with it (up, down, left or right; a diagonal hop is never a cut). Reading the marks in the order the trail occupies them must reproduce mark_run from front to back, and one trail may not occupy the same square twice.

Marks are case sensitive, so "g" and "G" count as different glyphs.

Return true when at least one such trail exists, and false when none does.

Examples

Example 1

Input
tablet = [["s","n","e"],["t","o","r"],["a","d","k"]], mark_run = "stone"
Output
true

One trail runs (0,0) -> (1,0) -> (1,1) -> (0,1) -> (0,2), picking up s, t, o, n, e in that order.

Example 2

Input
tablet = [["s","n","e"],["t","o","r"],["a","d","k"]], mark_run = "stored"
Output
false

Every trail spelling s, t, o, r, e reaches the square holding e in the top right corner, and no square beside it carries d.

Example 3

Input
tablet = [["h","i"]], mark_run = "hih"
Output
false

Only two squares exist, so the third mark would have to reuse the square already occupied by the first, which a trail may not do.

Constraints

  • rows == tablet.length
  • cols == tablet[r].length
  • 1 <= rows, cols <= 6
  • 1 <= mark_run.length <= 15
  • Every entry of tablet and every character of mark_run is a single uppercase or lowercase English letter.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def trail_exists(tablet: list[list[str]], mark_run: str) -> bool:
Java
public boolean trailExists(char[][] tablet, String mark_run)

More on the same topics