leetExpert
Practice

Word Search

Module 15 · Matrix / 2D Traversal

Problem

Given an m × n grid of characters board and a string word, return true if word exists in the grid as a path of adjacent cells (horizontally or vertically neighboring — no diagonals), where the same cell cannot be used more than once within a single word. (LeetCode 79.)

Examples

Example 1

Inputboard = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"Outputtrue

Example 2

Inputboard = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"Outputtrue

Example 3

Inputboard = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"Outputfalse

Explanation. would reuse a cell

Constraints

1 ≤ m, n ≤ 6, 1 ≤ word.length ≤ 15.

Attempt it first

This is a grid DFS like Number of Islands, but the goal is different: instead of exploring an entire connected region once, you're trying every possible path that spells word, and abandoning a path the moment it can't work. That "try a path, and if it fails, undo and try a different one" shape should sound familiar even before Module 16 (Recursion & Backtracking) formally names it. Before opening anything, work out: what has to be undone when a path attempt fails, and why does skipping that step break the next attempt, not the current one?