How do you approach Word Search?

Use DFS/backtracking starting from each cell.

What is the time complexity of Word Search?

Time complexity: O(m n 4^L) where L is the word length. Space complexity: O(L) for recursion stack.

What are common mistakes on Word Search?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Word Search

MediumAlgorithms

Description

Given an `m x n` grid of characters `board` and a string `word`, return `true` if `word` exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

Example 2

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output: true

Example 3

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output: false

Constraints

- m == board.length - n = board[i].length - 1 <= m, n <= 6 - 1 <= word.length <= 15 - board and word consists of only lowercase and uppercase English letters.

Word Search: approach, complexity and pitfalls

A medium backtracking problem, graded against 6 test cases (3 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

More Backtrackingproblems →

If you are stuck

Show the 3-step hint ladder

Use DFS/backtracking starting from each cell.
Mark cells as visited during the search to avoid reuse.
Restore the cell after backtracking.

The optimal approach

Show the approach: Backtracking/DFS

Try starting from each cell. Use DFS to explore all paths, marking visited cells temporarily.

Time: O(m * n * 4^L) where L is the word length
Space: O(L) for recursion stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

← Back to problems

Word Search

MediumAlgorithms

Description

Example 1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

Example 2

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output: true

Example 3

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output: false

Constraints

- m == board.length - n = board[i].length - 1 <= m, n <= 6 - 1 <= word.length <= 15 - board and word consists of only lowercase and uppercase English letters.

Word Search: approach, complexity and pitfalls

A medium backtracking problem, graded against 6 test cases (3 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

More Backtrackingproblems →

If you are stuck

Show the 3-step hint ladder

Use DFS/backtracking starting from each cell.
Mark cells as visited during the search to avoid reuse.
Restore the cell after backtracking.

The optimal approach

Show the approach: Backtracking/DFS

Try starting from each cell. Use DFS to explore all paths, marking visited cells temporarily.

Time: O(m * n * 4^L) where L is the word length
Space: O(L) for recursion stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.