Word Search

Find word in 2D grid with backtracking and board marking.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Problem

Given m×n board of characters and a word, determine if word exists in grid. Word constructed from adjacent cells (horizontal/vertical). Same cell cannot be used more than once.

DFS Backtracking

For each cell matching first letter, start DFS. At each step, check bounds, match current char. Mark visited (modify board or use visited set). Recurse to 4 neighbors. Restore on backtrack.

Goword-search.go

37 linesLn 1, Col 1Go

Modify board in-place to mark visited (save/restore char). Try all 4 directions. Early return on success. O(m×n×4^L) worst case.

Optimizations

Frequency check: If word has more of a char than board, return false immediately.
Reverse word: If last char is rarer than first, reverse word and search from end.
Pruning: If remaining cells < remaining word length, return false.
Direction ordering: Try directions likely to succeed first (e.g., toward center).
Visited array vs board modification: Board mod saves O(mn) space; visited array cleaner.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.