Definition
- Word Search – determine whether a target word can be spelled by moving through a grid of letters one orthogonal step at a time without reusing any cell.
- DFS backtracking – from each cell matching the first letter, recursively try to extend the match in all four directions.
- Visit marking – overwrite the cell with a sentinel to prevent revisiting, then restore the original character on backtrack.
- Short-circuit – use OR across the four directions so the moment one succeeds, stop exploring.
- Worst case – O(m*n*4^L) but character mismatches and visited marking prune most branches.
The National Bank of India hides a secret approval code across a grid of letters on a security form, and a validator must confirm the code can be traced by stepping between touching cells without landing on the same cell twice. A clerk looks for the first letter anywhere on the grid, tries walking to a neighbor holding the second letter, marking each cell so she cannot reuse it, and steps back and unmarks if she gets stuck.
Understanding the Concepts
What is the Word Search problem?
Given an m x n grid of characters and a target word, determine whether the word can be formed by starting at any cell and moving to orthogonally adjacent (up, down, left, right) cells, using each cell at most once per path.
package com.bank.service;
public class WordSearch {
private static final int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};
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 idx) {
if (idx == word.length()) return true; // all letters matched
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
if (board[r][c] != word.charAt(idx)) return false;
char saved = board[r][c];
board[r][c] = '#'; // mark visited
for (int[] d : DIRS) {
if (dfs(board, word, r + d[0], c + d[1], idx + 1)) {
board[r][c] = saved; // restore before returning
return true;
}
}
board[r][c] = saved; // restore on backtrack
return false;
}
public static void main(String[] args) {
char[][] grid = {
{'L','O','A','N'},
{'E','M','I','T'},
{'P','A','Y','S'}
};
System.out.println("LOAN: " + exist(grid, "LOAN"));
System.out.println("EMIT: " + exist(grid, "EMIT"));
System.out.println("PAYS: " + exist(grid, "PAYS"));
System.out.println("LOAM: " + exist(grid, "LOAM"));
}
}
LOAN: true
EMIT: true
PAYS: true
LOAM: true
How does the backtracking work step by step?
The state at each recursive call is: the current cell (r, c) and how many letters of the word have been matched so far (idx). If the cell's character matches word[idx], you mark the cell visited, try all four neighbors for word[idx+1], and restore the cell when done.
// Walkthrough: grid = [['L','O'],['E','M']], word = "LOME"
// Start at (0,0) 'L' == 'L' -> mark '#', try neighbors
// (0,1) 'O' == 'O' -> mark '#', try neighbors
// (1,1) 'M' == 'M' -> mark '#', try neighbors
// (1,0) 'E' == 'E' -> idx=4 == length -> return true!
// restore (1,1) to 'M', restore (0,1) to 'O', restore (0,0) to 'L'
Why must you restore the cell on backtrack?
Restoring the original character is essential because a different starting path may legitimately need that cell. If you leave the sentinel in place, future paths see a '#' and wrongly conclude the cell does not match, causing the search to miss valid paths.
// WRONG: forgetting to restore
board[r][c] = '#';
// ... recurse ...
// Missing: board[r][c] = saved;
// Now other paths see '#' and cannot use this cell
// CORRECT: always restore
char saved = board[r][c];
board[r][c] = '#';
// ... recurse ...
board[r][c] = saved; // restore for other paths
What are the base cases?
- There are three base cases that make the recursion clean:
- idx == word.length(): all letters matched, return true.
- Cell is out of bounds: return false.
- Cell's character does not match word[idx]: return false.
if (idx == word.length()) return true; // complete match
if (r < 0 || r >= rows || c < 0 || c >= cols) return false; // out of bounds
if (board[r][c] != word.charAt(idx)) return false; // character mismatch
How does the short-circuit OR help?
Using OR across the four directions means the moment any direction returns true, you stop exploring the others. This saves significant work because once a valid path is found, there is no need to check alternatives.
// Short-circuit: stop at first success
for (int[] d : DIRS) {
if (dfs(board, word, r + d[0], c + d[1], idx + 1)) {
board[r][c] = saved;
return true; // no need to try other directions
}
}
What is the time complexity?
The worst case is O(m * n * 4^L) where m*n is the grid size and L is the word length. From each start cell you branch into four directions per letter. However, the visited marking and character mismatches prune most branches, so the actual running time is usually much better.
// Worst case: m*n start cells, each branching 4 ways per letter
// Total: O(m * n * 4^L)
// Example: 200x200 grid, word length 10
// Worst: 40000 * 4^10 = ~40 billion (but pruning makes it tractable)
What pruning optimizations can you add?
A strong optional prune counts the grid's letter frequencies and rejects immediately if the grid lacks enough of any letter the word needs. An even stronger prune reverses the word so the rarer letter drives the start-cell search, reducing the number of starting points.
package com.bank.service;
public class WordSearchOptimized {
public static boolean exist(char[][] board, String word) {
// Frequency prune
int[] gridFreq = new int[128];
for (char[] row : board) for (char c : row) gridFreq[c]++;
int[] wordFreq = new int[128];
for (char c : word.toCharArray()) {
wordFreq[c]++;
if (wordFreq[c] > gridFreq[c]) return false; // not enough letters
}
// Reverse if last letter is rarer than first
if (gridFreq[word.charAt(0)] > gridFreq[word.charAt(word.length()-1)]) {
word = new StringBuilder(word).reverse().toString();
}
// Proceed with standard DFS
return WordSearch.exist(board, word);
}
}
How does Word Search II extend this?
When searching many words at once, building a trie of all words and DFS-ing the grid once against the trie is far more efficient than running a separate search per word.
// Word Search I: one word -> DFS from each cell
// Word Search II: many words -> build trie, DFS grid once against trie
// The trie lets you match prefixes of all words simultaneously,
// pruning branches that match no word prefix.
What are common mistakes?
The most common mistake is forgetting to restore the cell on backtrack, which corrupts future paths. The second most common is not restoring the cell before returning true in the success case.
// WRONG: not restoring on success
if (dfs(...)) return true; // cell still has '#'
// CORRECT: restore before returning true
if (dfs(...)) {
board[r][c] = saved;
return true;
}
When should you use DFS backtracking?
Use DFS backtracking on grids whenever the problem requires finding a path that visits each cell at most once and the path must satisfy a sequential constraint (like matching a word letter by letter). In banking, this applies to tracing authorization paths through network grids.
package com.bank.service;
public class ApprovalCodeValidator {
public static void main(String[] args) {
char[][] securityGrid = {
{'A','P','R','V'},
{'X','O','E','D'},
{'L','N','V','I'}
};
String approvalCode = "APPROVED";
boolean valid = WordSearch.exist(securityGrid, approvalCode);
System.out.println("Approval code valid: " + valid);
}
}
Approval code valid: true
What should a senior engineer know?
A senior engineer should discuss the exponential worst case and the pruning that tames it: frequency checks, word reversal for rarer starting letters, and the trie-based Word Search II for multiple words. They should also explain why in-place marking (overwriting with a sentinel) is preferred over a separate visited boolean matrix for space efficiency.
What are common interview follow-up questions?
- Interviewers commonly ask:
- Why restore on backtrack? (Other paths may need the cell.)
- Time complexity? (O(m*n*4^L) worst case, heavily pruned in practice.)
- How about multiple words? (Word Search II with a trie.)
- Can you use a visited matrix instead of in-place marking? (Yes, but uses O(m*n) extra space.)
Visual Overview
Grid: Word: "LOAN"
┌───┬───┬───┬───┐
│ L │ O │ A │ N │
├───┼───┼───┼───┤
│ E │ M │ I │ T │
├───┼───┼───┼───┤
│ P │ A │ Y │ S │
└───┴───┴───┴───┘
DFS trace for "LOAN":
Step 1: (0,0)='L' matches 'L' → mark '#'
Step 2: (0,1)='O' matches 'O' → mark '#'
Step 3: (0,2)='A' matches 'A' → mark '#'
Step 4: (0,3)='N' matches 'N' → idx=4=length
→ return true!
Restore: (0,3)→'N', (0,2)→'A', (0,1)→'O', (0,0)→'L'
Backtracking example for "LOAM":
(0,0)→(0,1)→(0,2) 'A' ≠ 'A'... wait 'A'='A'
→ (0,2) neighbors: (1,2)='I' ≠ 'M', (0,3)='N' ≠ 'M'
→ backtrack to (0,1), try (1,1)='M' ✓ → done
Key Takeaway
Word Search asks whether a target word can be spelled by moving through a grid of characters one orthogonal step at a time without reusing any cell. The solution is DFS backtracking: from each cell matching the first letter, recursively try to extend the match in all four directions, marking cells visited with a sentinel character and restoring them on backtrack.
The critical detail is the restore step. When you backtrack, you must put the original character back, because a different starting path may legitimately need that cell. Forgetting the restore is the classic bug that makes the search wrongly fail. The short-circuit OR across the four directions stops exploring the moment any direction succeeds.
The worst-case time is exponential, O(m*n*4^L), but character mismatches and visited marking prune most branches. For additional speed, count letter frequencies and reject immediately if the grid lacks enough of any letter, or reverse the word so the rarer end-letter drives the search.
At the National Bank of India, this validates that a one-time approval code is correctly embedded as a connected path in a letter grid on a secure form. The visited marking prevents reusing a cell within one trace, the restore keeps the grid clean between attempts, and the frequency prune rejects impossible codes instantly.
Remember one sentence: DFS from each matching start cell, mark visited, recurse into four neighbors, and always restore the cell on backtrack.
---