Definition
Word Search uses depth-first search with backtracking on a character grid.
- Grid traversal tries every cell as a possible starting point for the word.
- DFS recursion matches the word character by character, moving to horizontally or vertically adjacent cells.
- Visited marking temporarily overwrites the cell with a sentinel to prevent revisiting within a single path.
- Backtracking restores the original character after exploring all four directions.
- Short-circuit returns true immediately once any path matches the full word.
Picture the National Bank of India's fraud team looking at a grid of letters pulled from scrambled transaction memos. They want to know if a suspicious codeword like FRAUD is hidden as a connected trail through adjacent cells. An investigator starts on an F, tries a neighbor that is R, then A, and so on. If a trail dead-ends, they step back and erase their footprints so another trail can reuse those cells.
Understanding the Concepts
What is the Word Search Problem?
Given an m x n board of characters and a string word, determine if the 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 cell may not be used more than once per path.
At National Bank of India, the fraud team searches for suspicious codewords hidden in grids of scrambled transaction memos.
package com.bank.service;
public class WordSearch {
public static boolean exist(char[][] board, String word) {
int rows = board.length, cols = board[0].length;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (dfs(board, word, r, c, 0)) return true;
}
}
return false;
}
private static boolean dfs(char[][] board, String word, int r, int c, int index) {
if (index == word.length()) return true; // matched all characters
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
if (board[r][c] != word.charAt(index)) return false;
char original = board[r][c];
board[r][c] = '#'; // mark visited
boolean found = dfs(board, word, r + 1, c, index + 1)
|| dfs(board, word, r - 1, c, index + 1)
|| dfs(board, word, r, c + 1, index + 1)
|| dfs(board, word, r, c - 1, index + 1);
board[r][c] = original; // backtrack: restore
return found;
}
public static void main(String[] args) {
char[][] board = {
{'F', 'R', 'A', 'U'},
{'X', 'D', 'B', 'C'},
{'G', 'H', 'I', 'J'}
};
System.out.println("FRAUD found: " + exist(board, "FRAUD"));
System.out.println("BANK found: " + exist(board, "BANK"));
}
}
FRAUD found: true
BANK found: false
Why Does This Problem Matter?
Word Search is the canonical grid backtracking problem. It teaches how to combine DFS with state management on a 2D grid, which applies to maze solving, flood fill, and pattern matching on grids. The visited-marking technique used here appears in many grid-based interview problems.
package com.bank.service;
public class GridPatterns {
// Same technique applies to:
// - Maze path finding (can we reach the exit?)
// - Flood fill (paint connected region)
// - Island counting (mark visited land cells)
// - Word Search II (find multiple words with Trie)
}
How Does the DFS with Backtracking Work?
The outer loop tries every cell as a starting point. From each start, the recursive DFS carries the current row, column, and the index into the word being matched. Three checks happen before exploring: bounds check, character match, and visited check.
To mark a cell as visited, we overwrite it with a sentinel character. After exploring all four directions, we restore the original character. This is the backtracking step.
package com.bank.core;
public class DFSTrace {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public static boolean dfs(char[][] board, String word, int r, int c, int idx, int depth) {
String indent = " ".repeat(depth);
if (idx == word.length()) {
System.out.println(indent + "MATCH COMPLETE");
return true;
}
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
|| board[r][c] != word.charAt(idx)) {
return false;
}
System.out.println(indent + "Visit (" + r + "," + c + ") = '" + board[r][c] + "'");
char orig = board[r][c];
board[r][c] = '#';
for (int[] d : DIRS) {
if (dfs(board, word, r + d[0], c + d[1], idx + 1, depth + 1)) {
board[r][c] = orig;
return true;
}
}
board[r][c] = orig; // backtrack
System.out.println(indent + "Backtrack (" + r + "," + c + ")");
return false;
}
}
How Is This Different from Word Search II?
| Aspect | Word Search (single word) | Word Search II (multiple words) |
|---|---|---|
| Input | One word to find | A list of words to find |
| Approach | DFS per starting cell for one word | Trie + DFS: one sweep for all words |
| Pruning | Character mismatch only | Trie prefix prunes entire branches |
| Efficiency | O(m*n*4^L) per word | O(m*n*4^L) total for all words |
| Collection | Return boolean | Collect all found words |
// Word Search: check one word
if (dfs(board, word, r, c, 0)) return true;
// Word Search II: walk Trie node during DFS
TrieNode next = node.children.get(board[r][c]);
if (next == null) return; // Trie prunes
What Are the Edge Cases?
Edge cases include: a word longer than the total number of cells (impossible), a single-cell grid, a word that requires using the same cell twice (impossible by rules), and a board where every cell is the same letter.
package com.bank.core;
public class WordSearchEdgeCases {
public static void main(String[] args) {
// Single cell board
char[][] single = {{'A'}};
System.out.println(WordSearch.exist(single, "A")); // true
System.out.println(WordSearch.exist(single, "AB")); // false
// All same letters
char[][] same = {{'A', 'A'}, {'A', 'A'}};
System.out.println(WordSearch.exist(same, "AAAA")); // true (path exists)
System.out.println(WordSearch.exist(same, "AAAAA")); // false (only 4 cells)
}
}
true
false
true
false
What Are Common Mistakes?
The first common mistake is forgetting to restore the character after backtracking. This causes cells to stay permanently marked, and valid words get rejected.
Wrong code:
// WRONG: never restores the cell
board[r][c] = '#';
boolean found = dfs(board, word, r + 1, c, index + 1);
return found; // BUG: board[r][c] stays '#' forever
Correct code:
// CORRECT: always restore
board[r][c] = '#';
boolean found = dfs(board, word, r + 1, c, index + 1);
board[r][c] = original; // restore even if found is true
return found;
The second mistake is not short-circuiting. Once any direction returns true, you should return immediately without exploring the remaining directions.
What About Time and Space Complexity?
The worst-case time complexity is O(m * n * 4^L) where m and n are the grid dimensions and L is the word length. From each cell, we branch into up to 4 directions for each character. In practice, the character matching prunes most branches quickly.
The space complexity is O(L) for the recursion depth, since we go at most L levels deep.
package com.bank.core;
public class WordSearchComplexity {
// Time: O(m * n * 4^L)
// m*n starting cells, up to 4^L paths from each
// Space: O(L) recursion depth
// L = word length (max recursion depth)
// In practice, much faster due to character mismatch pruning
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly follow up with:
- Word Search II: find multiple words using a Trie for prefix pruning.
- Can you solve this without modifying the board? Use a visited boolean matrix instead of overwriting cells.
- Optimize for a very long word: check if the board contains enough of each required character before starting DFS.
- Allow diagonal movement: add four more direction vectors to the direction array.
package com.bank.core;
public class WordSearchOptimization {
// Pre-check: count character frequencies
public static boolean canContain(char[][] board, String word) {
int[] boardFreq = new int[128];
int[] wordFreq = new int[128];
for (char[] row : board) for (char c : row) boardFreq[c]++;
for (char c : word.toCharArray()) wordFreq[c]++;
for (int i = 0; i < 128; i++) {
if (wordFreq[i] > boardFreq[i]) return false;
}
return true;
}
}
Visual Overview
Grid:
┌───┬───┬───┬───┐
│ F │ R │ A │ U │
├───┼───┼───┼───┤
│ X │ D │ B │ C │
├───┼───┼───┼───┤
│ G │ H │ I │ J │
└───┴───┴───┴───┘
Finding "FRAUD":
Step 1: Start at (0,0)='F' -> match F
Step 2: Move right to (0,1)='R' -> match R
Step 3: Move right to (0,2)='A' -> match A
Step 4: Move right to (0,3)='U' -> match U
Step 5: Move down to (1,3)='C' -> no match for D
Backtrack to (0,3)
Cannot find D adjacent to U -> backtrack further
Actual path for FRAUD:
F(0,0) -> R(0,1) -> A(0,2) -> move needs U and D
The path snakes through adjacent cells.
Key Takeaway
Word Search asks whether a given word can be formed in a grid of characters by moving between horizontally or vertically adjacent cells, where each cell can be used at most once within a single path. The natural solution is depth-first search combined with backtracking, which means I explore one candidate trail as deeply as possible, and whenever a trail fails I step back and undo my changes so the cells become available for other trails.
Concretely, I try every cell in the grid as a possible starting point, and from each start I run a recursive search that carries the current row, the current column, and the index of the character in the word I am trying to match. The search succeeds when the index reaches the length of the word, and it fails when I go out of bounds, when the cell does not match the expected character, or when the cell is already part of the current path.
The key detail is how I mark a cell as used and then release it. A clean trick is to temporarily overwrite the cell with a sentinel character so the mismatch check naturally rejects it during this path, and then to restore the original character after exploring all four directions. That restoration is the backtracking step, and forgetting it is the classic bug.
In my project at National Bank of India, the anti-fraud unit searched grids of characters pulled from obfuscated wire-transfer memos for suspicious codewords hidden as connected trails through adjacent cells. The DFS with backtracking confirmed whether a specific codeword was present without ever double-counting a single letter inside one trail.
Remember one sentence: DFS matches the word character by character through adjacent cells, marking cells visited and restoring them on backtrack.
---