Explain Word Search on a board (backtracking).

Short answer: DFS from each cell matching the first letter. Mark visited, explore 4 directions for the next character, then unmark (backtrack). Return true as soon as the word is completed.

Complexity

Time roughly O(N * 4^L) worst case (N cells, L word length); Space O(L) recursion.

Edge cases to mention

• Word longer than board cells
• Reuse of same cell (forbidden)
• Single-letter word

Emphasize marking/unmarking — that is the backtracking signature.