Word Search

Word Search

What is this problem about?

"Word Search" is a grid-based puzzle. You are given an m x n board of characters and a string word. You need to determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontal or vertical), and the same letter cell may not be used more than once in a single word.

Why is this asked in interviews?

This is one of the most popular DFS on 2D Matrix problems. It tests your ability to navigate a grid, handle boundaries, and implement backtracking to explore multiple paths. It is asked by almost everyone, from Amazon and Apple to startup unicorns.

Algorithmic pattern used

The pattern is Depth-First Search (DFS) with Backtracking.

1. Iterate through every cell in the grid.
2. If the cell matches the first letter of the word, start a DFS.
3. In DFS, mark the current cell as "visited" (e.g., by changing it to a special character).
4. Recursively check the four neighbors (Up, Down, Left, Right) for the next letter.
5. If the next letter is found, continue. If not, unmark the current cell (backtrack) and return false.

Example explanation

Grid:

A B C
D E F

Word: ABED.

1. Start at (0,0): 'A'. Match!
2. Neighbors of (0,0): 'B' at (0,1) is a match!
3. Neighbors of (0,1): 'E' at (1,1) is a match!
4. Neighbors of (1,1): 'D' at (1,0) is a match! Word found!

Common mistakes candidates make

• Not unmarking visited cells: If you don't backtrack the "visited" status, you won't be able to use that cell in a different path that might actually be the correct one.
• Redundant Search: Not returning immediately when the word is found, continuing to search other cells.
• Index Out of Bounds: Forgetting to check if r < 0 or c >= cols before accessing the grid.

Interview preparation tip

For grid DFS, always check three things at the start of your recursive function:

1. Is the current index out of bounds?
2. Does the current cell match the target character?
3. Have we already visited this cell? This keeps your code clean and prevents errors.