MediumSubsets

Word Search

Explanation & Solution

Description

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same cell may not be used more than once.

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

Explanation: The word "ABCCED" can be traced starting from the top-left 'A', moving right to 'B', right to 'C', down to 'C', left to 'E' (but actually down to 'E'), then left to 'D'.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consist of only lowercase and uppercase English letters

Approach

Subsets pattern

1. Iterate Through Every Cell

Loop through each cell (r, c) in the board
Try starting the word search from each cell by calling dfs(r, c, 0)
If any starting cell leads to a complete match, return true

2. DFS Base Cases

If i === word.length, we have matched every character — return true
If (r, c) is out of bounds, return false
If board[r][c] !== word[i], the current cell does not match the next needed character — return false

3. Mark the Cell as Visited

Save the current cell value in temp
Replace board[r][c] with '#' to mark it as visited
This prevents the same cell from being used twice in the same path

4. Explore All Four Directions

Recursively search down, up, right, and left with i + 1
Use short-circuit evaluation (||) so we stop early once any direction finds a valid path

5. Backtrack

After exploring all directions, restore board[r][c] to its original value (temp)
This allows the cell to be used in other search paths starting from different positions

Key Insight

The key technique is backtracking: we temporarily mark cells as visited during exploration, then restore them when we backtrack, allowing the same cell to be considered in different paths

Time

O(m * n * 4^L) where L is the word length — for each starting cell we may explore up to 4 directions at each step

Space

O(L)the recursion stack depth equals the word length

Visualization

Input:

Backtracking Search3×4 grid

output—

Press play to start backtracking search

CurrentQueuedVisitedSource

8 steps

Solution Code

Palindrome Partitioning

Generalized Abbreviation