AdvancedBacktrackingArrays
Word Search
Problem
Given an m × n grid of characters board and a string word, return true if word can be constructed from letters of sequentially adjacent cells. Adjacent cells are horizontal or vertical neighbours, and the same cell may not be used more than once in a single word.
Constraints
- 1 ≤ m, n ≤ 6
- 1 ≤ word.length ≤ 15
- board and word consist of lowercase and uppercase English letters
Examples
in: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
out: true
in: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
out: false
The only B cannot be reused.
What this tests
- Recognising an exhaustive search with constraints — backtracking
- Marking and unmarking state (the "undo" step)
- Pruning: character mismatch, bounds, visited cells
- Exponential complexity analysis that is honest about branching factor
- Small-constraint reading (m, n ≤ 6 signals brute force is intended)
Systematic ReasoningImplementationOptimizationEdge CasesComplexity Analysis
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
You must find which of 10^4 words appear on the board (Word Search II).
F2
What pruning would you add for a large board with a long word?
F3
Cells may now be reused, and adjacency includes diagonals. What changes?
F4
Return the path (list of coordinates), not just true/false.