DSA interview question

Word Search

Hard · Algorithms · Topics: recursion, backtracking, matrix

The problem

A word-puzzle game shows a grid of letters, and the player claims a word is hidden in it. The word must be traced through horizontally or vertically adjacent cells, and no cell may be used twice in the same word. The game must verify the claim instantly. The standard approach is backtracking DFS from every cell that matches the first letter: step to a neighbour matching the next letter, mark the current cell as used while exploring deeper, and unmark it when backing out so other paths can use it.

Example: grid ABCE / SFCS / ADEE, word "ABCCED" → true.

Function signature

bool exist(vector<vector<char>>& board, const string& word);

Test cases

Input `(board, word)`	Output	Explanation
`(ABCE/SFCS/ADEE, "ABCCED")`	`true`	A→B→C→C→E→D
`(ABCE/SFCS/ADEE, "SEE")`	`true`
`(ABCE/SFCS/ADEE, "ABCB")`	`false`	The B can't be reused
`(a, "a")`	`true`	A 1 × 1 grid
`(ab/cd, "abdc")`	`true`	a→b→d→c
`(ab/cd, "abcd")`	`false`	b and c aren't adjacent

(Confirm: moves are up, down, left and right only, no diagonals; each cell is used at most once per word; the board is restored afterwards.)

How interviewers phrase it

"Given an m x n grid of characters and a string word, return true if word exists in the grid" (LeetCode 79).
Many words at once is Word Search II (LeetCode 212), which uses a trie.

Clarifying questions to ask

Are diagonal moves allowed? (No.)
Can a cell be reused within one word? (No.)
May I modify the board temporarily? (Yes, if it's restored.)

Follow-ups to expect

"How do you mark visited cells?"
"Why must you restore the cell?"
"What pruning helps?"
"Complexity?"
"How do you search for many words?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview