Word Search - Video Solutions

Problem Overview: Given an m x n character grid and a target word, determine whether the word exists in the grid. You can move horizontally or vertically to adjacent cells, and each cell can be used only once in the current path. The challenge is efficiently exploring possible paths while preventing revisiting cells.

Approach 1: DFS with Backtracking (O(m * n * 4^L) time, O(L) space)

This approach treats the grid like a graph and performs a depth‑first search from every cell that matches the first character of the word. From each position, recursively explore up, down, left, and right while checking whether the next character matches the word. A temporary mark (such as replacing the character or using a visited set) prevents revisiting the same cell in the current path. If a path fails, restore the cell and backtrack to try another direction.

The key insight is that you only explore paths that match the word prefix. The branching factor is at most 4 directions, and recursion depth equals the word length L. This pruning keeps the search manageable even though the theoretical worst case is exponential. DFS with backtracking is the most common interview solution for problems involving path exploration in a matrix combined with constraint-based search from backtracking.

Approach 2: BFS with Queue and Pruning (O(m * n * 4^L) time, higher space)

This variation explores possible paths level by level using a queue. Each queue state stores the current cell, index in the word, and the set or mask of visited cells. Start BFS from every grid cell that matches the first character, then expand to neighbors that match the next character. States that violate constraints (character mismatch or revisiting a cell) are pruned immediately.

BFS guarantees that all prefixes of the word are explored systematically. However, the queue can grow large because multiple partial paths are stored simultaneously, increasing memory usage compared to DFS recursion. This approach is less common in interviews but useful when you want explicit control over state exploration or iterative traversal instead of recursion.

Both approaches rely heavily on efficient grid traversal and prefix matching. The board itself is typically represented as a 2D array, and the target pattern is a string that must be matched sequentially.

Recommended for interviews: DFS with backtracking is the expected solution. Interviewers look for correct recursion structure, proper visited handling, and early pruning when characters do not match. Starting DFS from each cell demonstrates full coverage of the grid, while backtracking shows you understand how to explore and undo state changes efficiently. BFS can work but usually consumes more memory and adds unnecessary complexity for this problem.