The Word Search problem is a classic interview question that tests recursion, grid traversal, and backtracking. In this blog, we’ll solve it two ways:
- Using a
Set
to track visited cells (clear and beginner-friendly). - Using an in-place optimization (cleaner and space-efficient).
📌 Problem Statement
We are given a 2D board of characters and a word. We need to check if the word exists in the board.
Rules:
- The word can be constructed from letters of adjacent cells (up, down, left, right).
- A cell cannot be used more than once in the same path.
Example:
Board:
A B C E
S F C S
A D E E
Word: "ABCCED"
Output: true
💡 Approach 1: Using a Set
The idea is simple:
- Try every cell
(r, c)
as a potential starting point. - Use DFS to explore neighbors.
- Keep a
Set
of visited cells (so we don’t revisit them). - Backtrack: after exploring, remove the cell from the
Set
.
✅ Code (with Set)
var exist = function (board, word) {
let rows = board.length;
let cols = board[0].length;
let pathSet = new Set();
const backtrack = (i, r, c) => {
if (i === word.length) return true;
if (r < 0 || c < 0 || r >= rows || c >= cols ||
board[r][c] !== word[i] ||
pathSet.has(r + "," + c)) {
return false;
}
pathSet.add(r + "," + c);
let res = backtrack(i + 1, r + 1, c) ||
backtrack(i + 1, r - 1, c) ||
backtrack(i + 1, r, c + 1) ||
backtrack(i + 1, r, c - 1);
pathSet.delete(r + "," + c); // backtrack cleanup
return res;
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (backtrack(0, r, c)) return true;
}
}
return false;
};
⚙️ Complexity (Set version)
-
Time Complexity:
- Worst case:
O(rows × cols × 4^L)
whereL
= length of the word.
- Worst case:
-
Space Complexity:
- The
Set
stores up toL
cells. - Recursion depth =
L
. - So O(L) extra space.
- The
This is intuitive and great for understanding recursion, but we can do better.
💡 Approach 2: Optimized In-Place Marking
Instead of maintaining a Set
, we can modify the board in-place:
- At each step, temporarily set the current cell to
"#"
to mark it visited. - Explore neighbors.
- Restore the original character when backtracking.
This way, “visited check” happens naturally because a "#"
will never match the next character in word
.
✅ Code (in-place optimization)
var exist = function (board, word) {
let rows = board.length;
let cols = board[0].length;
const backtrack = (i, r, c) => {
if (i === word.length) return true;
if (r < 0 || c < 0 || r >= rows || c >= cols ||
board[r][c] !== word[i]) {
return false;
}
// Mark visited by modifying the board
let temp = board[r][c];
board[r][c] = "#";
let res = backtrack(i + 1, r + 1, c) ||
backtrack(i + 1, r - 1, c) ||
backtrack(i + 1, r, c + 1) ||
backtrack(i + 1, r, c - 1);
// Restore for other paths
board[r][c] = temp;
return res;
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (backtrack(0, r, c)) return true;
}
}
return false;
};
⚙️ Complexity (Optimized version)
-
Time Complexity:
Still
O(rows × cols × 4^L)
. -
Space Complexity:
Only recursion depth → O(L).
No
Set
, no extra storage. Cleaner and faster.
🔑 Comparison
Feature | With Set | In-place Optimization |
---|---|---|
Clarity | ✅ Easy to follow | ⚡ Cleaner, shorter |
Extra Space | O(L) (Set) | O(1) extra |
Speed | Slightly slower | Faster in practice |
Interview value | Good starter | Impressive finish |
✨ Takeaways
- Set approach: Great for beginners, shows clear backtracking logic.
- In-place approach: Professional, space-efficient, and elegant.
- Both methods teach the importance of backtracking cleanup — the trick that makes recursion work correctly.
👉 In an interview, I’d start with the Set approach to explain my thought process, then optimize to the in-place version to show deeper problem-solving skills.
Top comments (0)