Log inSign up
mediumLeetCodeNot Started

Word Search

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

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
Explanation: Path: (0,0) "A" -> (0,1) "B" -> (0,2) "C" -> (1,2) "C" -> (2,2) "E" -> (2,1) "D".

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation: Path: (1,3) "S" -> (2,3) "E" -> (2,2) "E".

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Explanation: Cannot reuse the cell "B" at (0,1) twice.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master in-place character masking (# or null character) to eliminate visited sets in grid backtracking.
  • Understand the 3L branching factor (since the previous cell cannot be revisited, branching is at most 3).
  • Apply frequency count heuristics and word reversal for dramatic pruning.

1. DFS with 2D Visited Array

Intuition

Maintain visited[r][c]. If board[r][c] == word[k] && !visited[r][c], mark visited[r][c] = true, recurse to neighbors, and reset on backtrack.

Algorithm

  1. Step 1: Iterate through every cell (r, c) in the grid to find matching word[0].
  2. Step 2: Maintain a 2D boolean array visited of size M x N.
  3. Step 3: Define dfs(r, c, k): if k == word.length return true.
  4. Step 4: From (r, c), explore 4 neighbors (Up, Down, Left, Right). If neighbor matches word[k] and is unvisited, recurse.
  5. Step 5: Backtrack by resetting visited[r][c] = false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 bool dfs(int r, int c, int k, const std::vector<std::vector<char>>& board, const std::string& word, std::vector<std::vector<bool>>& visited) {
8 if (k == (int)word.length()) return true;
9 if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size()) return false;
10 if (visited[r][c] || board[r][c] != word[k]) return false;
11
12 visited[r][c] = true;
13 bool found = dfs(r + 1, c, k + 1, board, word, visited) ||
14 dfs(r - 1, c, k + 1, board, word, visited) ||
15 dfs(r, c + 1, k + 1, board, word, visited) ||
16 dfs(r, c - 1, k + 1, board, word, visited);
17 visited[r][c] = false;
18 return found;
19 }
20
21 bool exist(std::vector<std::vector<char>>& board, std::string word) {
22 int m = board.size(), n = board[0].size();
23 std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
24
25 for (int i = 0; i < m; i++) {
26 for (int j = 0; j < n; j++) {
27 if (board[i][j] == word[0] && dfs(i, j, 0, board, word, visited)) {
28 return true;
29 }
30 }
31 }
32 return false;
33 }
34};
35
36int main() {
37 Solution solver;
38 std::vector<std::vector<char>> board = {
39 {'A','B','C','E'},
40 {'S','F','C','S'},
41 {'A','D','E','E'}
42 };
43 std::cout << "Word 'ABCCED' exists: " << (solver.exist(board, "ABCCED") ? "true" : "false") << "\n";
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(M * N * 3^L) — Explores paths up to length L with branching factor 3 at each step.
  • Space complexity: O(M * N + L) — O(M*N) memory for the visited matrix.

2. In-Place Character Masking Backtracking

Intuition

Replaces the visited boolean matrix by temporarily saving char temp = board[r][c] and setting board[r][c] = '#'. Since '#' will never match any alphabet in word, the current cell cannot be revisited in child calls.

Algorithm

  1. Step 1: Mark visited cells in-place by setting board[r][c] = # upon entry.
  2. Step 2: In dfs(r, c, k): if k == word.length return true.
  3. Step 3: Check bounds: if r < 0, r >= m, c < 0, c >= n or board[r][c] != word[k], return false.
  4. Step 4: Save temp = board[r][c] and set board[r][c] = #.
  5. Step 5: Recurse into 4 neighbors: dfs(r+1,c,k+1) || dfs(r-1,c,k+1) || dfs(r,c+1,k+1) || dfs(r,c-1,k+1).
  6. Step 6: Restore board[r][c] = temp and return true if any neighbor succeeded.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 bool dfs(int r, int c, int k, std::vector<std::vector<char>>& board, const std::string& word) {
8 if (k == (int)word.length()) return true;
9 if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size() || board[r][c] != word[k]) {
10 return false;
11 }
12
13 char temp = board[r][c];
14 board[r][c] = '#'; // Mark visited
15
16 bool found = dfs(r + 1, c, k + 1, board, word) ||
17 dfs(r - 1, c, k + 1, board, word) ||
18 dfs(r, c + 1, k + 1, board, word) ||
19 dfs(r, c - 1, k + 1, board, word);
20
21 board[r][c] = temp; // Restore state
22 return found;
23 }
24
25 bool exist(std::vector<std::vector<char>>& board, std::string word) {
26 int m = board.size(), n = board[0].size();
27 for (int i = 0; i < m; i++) {
28 for (int j = 0; j < n; j++) {
29 if (board[i][j] == word[0] && dfs(i, j, 0, board, word)) {
30 return true;
31 }
32 }
33 }
34 return false;
35 }
36};
37
38int main() {
39 Solution solver;
40 std::vector<std::vector<char>> board = {
41 {'A','B','C','E'},
42 {'S','F','C','S'},
43 {'A','D','E','E'}
44 };
45 std::cout << "Word exists: " << (solver.exist(board, "SEE") ? "true" : "false") << "\n";
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(M * N * 3^L) — Branching factor is strictly at most 3 since parent cell is marked.
  • Space complexity: O(L) — Recursion depth is bounded by length of word L.

3. In-Place DFS + Frequency Pruning & Word Reversal (Gold Standard)

Intuition

Count character frequencies in board. If boardCount[ch] < wordCount[ch], return false in O(M*N) time without running DFS. If boardCount[word[0]] > boardCount[word[L-1]], reverse word to start searching from the rarer letter, minimizing initial branch explosion.

When to apply: Gold standard optimal: Frequency pruning + reverse search optimization + in-place DFS.

Algorithm

  1. Step 1: Frequency pruning: Count character frequencies in board vs word. If board lacks any required character, return false immediately.
  2. Step 2: Directional optimization: If frequency(word[0]) > frequency(word[last]), reverse word to start search from rarer character.
  3. Step 3: Iterate through cells (r, c). When board[r][c] == word[0], start in-place DFS.
  4. Step 4: In dfs(r, c, k): if k == word.length return true.
  5. Step 5: Mark board[r][c] = #, recurse 4 directions, restore board[r][c] = temp.
  6. Step 6: Return true immediately once word is found.

Grid Character Path Search Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Find matching start character 'A' at cell (0, 0)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
r0
A*
↑ k=0
B
C
E
S
F
C
S
A
D
E
E
Variables at this step
matchedPrefix
A
cell
[0,0]
Check / comparison
board[0][0] == 'A' (word[0]) -> MATCH!
Decision / next transition
Mark cell (0,0) = '#', search for word[1] = 'B'
Why this step matters

Find matching start character A at cell (0, 0). Mark (0, 0) = # and search for B.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <algorithm>
6
7class Solution {
8public:
9 bool dfs(int r, int c, int k, std::vector<std::vector<char>>& board, const std::string& word) {
10 if (k == (int)word.length()) return true;
11 if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size() || board[r][c] != word[k]) {
12 return false;
13 }
14
15 char temp = board[r][c];
16 board[r][c] = '#';
17
18 bool found = dfs(r + 1, c, k + 1, board, word) ||
19 dfs(r - 1, c, k + 1, board, word) ||
20 dfs(r, c + 1, k + 1, board, word) ||
21 dfs(r, c - 1, k + 1, board, word);
22
23 board[r][c] = temp;
24 return found;
25 }
26
27 bool exist(std::vector<std::vector<char>>& board, std::string word) {
28 int m = board.size(), n = board[0].size();
29 if ((int)word.length() > m * n) return false;
30
31 std::unordered_map<char, int> boardFreq, wordFreq;
32 for (const auto& row : board) {
33 for (char ch : row) boardFreq[ch]++;
34 }
35 for (char ch : word) {
36 wordFreq[ch]++;
37 if (wordFreq[ch] > boardFreq[ch]) return false; // Early pruning
38 }
39
40 // Reverse word if tail is rarer than head
41 if (boardFreq[word.front()] > boardFreq[word.back()]) {
42 std::reverse(word.begin(), word.end());
43 }
44
45 for (int i = 0; i < m; i++) {
46 for (int j = 0; j < n; j++) {
47 if (board[i][j] == word[0] && dfs(i, j, 0, board, word)) {
48 return true;
49 }
50 }
51 }
52 return false;
53 }
54};
55
56int main() {
57 Solution solver;
58 std::vector<std::vector<char>> board = {
59 {'A','B','C','E'},
60 {'S','F','C','S'},
61 {'A','D','E','E'}
62 };
63 std::cout << "Optimal Word Search result: " << (solver.exist(board, "ABCCED") ? "true" : "false") << "\n";
64 return 0;
65}

Time & Space Complexity

  • Time complexity: O(M * N + M * N * 3^L) — Instant rejection of missing letters; minimal branching on valid letters.
  • Space complexity: O(L) — O(L) recursion call stack depth.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS with 2D Visited Boolean MatrixO(M * N * 3^L)O(M * N + L)Track visited cells in a 2D boolean array.Memory allocation overhead
2.In-Place DFS Backtracking (Better)O(M * N * 3^L)O(L)Mask cell board[r][c] = '#' and unmask on return.Worst-case branch factor
3.In-Place DFS + Frequency Pruning & Word Reversal (Optimal)OptimalO(M * N * 3^L)O(L)Check character counts in board. If board count < word count, return false immediately. Reverse word if tail is rarer than head.Optimal search tree

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to restore board[r][c] = temp when backtracking, permanently destroying board state for subsequent searches.

Pitfall 2:

Allocating a brand new visited matrix on every single cell loop iteration.

Crucial Edge Cases to Validate:

  • word.length > m * n -> impossible to form without cell reuse, returns false immediately.
  • Single cell board (1x1) matching single char word -> returns true.
  • Word has characters not present in the board -> frequency count pre-check rejects in O(M*N).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention in-place masking (board[r][c] = '#') right away to demonstrate memory efficiency.
  2. Proactively offer the character frequency pre-check optimization to impress interviewers with production-grade performance instincts.
  3. Transition naturally to Word Search II (Trie + DFS) if asked how to search for 10,000 words simultaneously.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the branching factor of Word Search 3 instead of 4 for steps after the first letter?

Back to DSA Sheet