March 24
Word Search
How to explore paths in a grid, mark the current choice, and undo that choice on the way back.
Backtracking Intermediate 25 min TypeScript
Given a matrix board of letters and a string word, return true if the word can be formed by adjacent letters in the grid.
Letters may connect horizontally or vertically.
The same cell cannot be used more than once in the same path.
Example:
Input:
board = [
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
word = "ABCCED"
Output: true
What to notice before coding
- The problem does not ask for the shortest path. It only asks whether one valid path exists.
- The "visited" state belongs to the current path, not to the whole board forever.
- Backtracking here is exactly try, mark, explore, and undo.
Common mistakes
- sharing the same visited set across independent attempts
- forgetting to undo the mark when unwinding recursion
Step 1 - Understand what must be controlled
The problem is not just "walk on the grid."
The real job is:
- walk the grid following the next needed letter
- without reusing the same cell in the same path
That already looks like DFS with backtracking.
Step 2 - Write the most direct baseline
The natural baseline is:
- try each cell as a starting point
- run DFS
- keep a
Hash Setof visited coordinates for the current path
It works and makes the reasoning visible.
Step 3 - Ask where the real state lives
"Visited" is not global.
It only belongs to the current attempt.
If one path fails, other attempts must still be allowed to reuse those cells.
That is why backtracking has to undo the mark on the way back.
Step 4 - Simplify the helper structure
Instead of keeping a Set, you can mark the board cell itself temporarily and then restore it.
Logically it is the same:
- mark
- explore
- undo
It just removes some overhead from each recursive call.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function exist(board: string[][], word: string): boolean {
// your solution here
return false
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(rows * cols * 4^word.length)
Space: O(word.length)
Solution 1 - DFS with a visited Hash Set
Good baseline because it makes the path state explicit.
export function exist(board: string[][], word: string): boolean {
const rows = board.length
const cols = board[0].length
function dfs(row: number, col: number, index: number, visited: Set<string>): boolean {
if (index === word.length) {
return true
}
const outOfBounds = row < 0 || row >= rows || col < 0 || col >= cols
if (outOfBounds || board[row][col] !== word[index]) {
return false
}
const key = `${row},${col}`
if (visited.has(key)) {
return false
}
visited.add(key)
const found =
dfs(row + 1, col, index + 1, visited) ||
dfs(row - 1, col, index + 1, visited) ||
dfs(row, col + 1, index + 1, visited) ||
dfs(row, col - 1, index + 1, visited)
visited.delete(key)
return found
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (dfs(row, col, 0, new Set())) {
return true
}
}
}
return false
}It works, but the Set adds extra work on every call.
Solution 2 - Backtracking by marking the grid in place
Now the state still stays local to the path, but without a coordinate helper structure.
export function exist(board: string[][], word: string): boolean {
const rows = board.length
const cols = board[0].length
function dfs(row: number, col: number, index: number): boolean {
if (index === word.length) {
return true
}
const outOfBounds = row < 0 || row >= rows || col < 0 || col >= cols
if (outOfBounds || board[row][col] !== word[index]) {
return false
}
const current = board[row][col]
board[row][col] = "#"
const found =
dfs(row + 1, col, index + 1) ||
dfs(row - 1, col, index + 1) ||
dfs(row, col + 1, index + 1) ||
dfs(row, col - 1, index + 1)
board[row][col] = current
return found
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (dfs(row, col, 0)) {
return true
}
}
}
return false
}The strong insight here is not just “use recursion.” It is controlling the right state in the right place with DFS plus backtracking.
What to say in the interview
A strong short explanation would be:
I try each cell as a starting point and run
DFSto match the word one letter at a time. The main constraint is not reusing the same cell in the current path. So I mark the choice before exploring neighbors and undo it when I return. That undo step is the actualbacktracking.
That shows that you:
- understood the role of path-local state
- can explain why undoing matters
- do not treat backtracking like magic
When this pattern shows up again
This pattern comes back when you need to:
- explore many possible paths
- maintain local constraints per attempt
- mark and restore state during
DFS - solve grid, combination, or search-with-pruning problems
The point is not memorizing
Word Search.
The point is learning that backtracking is disciplined exploration, not blind guessing.