Grid Lexicon Verification — Problem Statement & Solution Guide
Problem Description
Given a 2D grid of characters and a list of words, determine if each word can be formed by traversing the grid, with the constraint that each cell can only be used once per word, and all movements are either horizontal or vertical.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Grid Lexicon Verification"
WHY DOES IT MATTER?
Backtracking with a Trie captures the "multiple‑query" pattern where many overlapping sub‑problems share prefixes. Recognizing this pattern prevents exponential blow‑up and is a cornerstone for any interview problem involving word search, pattern matching, or combinatorial enumeration on grids.
OPTIMIZATION CHALLENGE
The key insight is to prune the search space early by checking prefix existence in the Trie; as soon as the current path does not correspond to any word prefix, the recursion backtracks, cutting off entire sub‑trees that would otherwise be explored needlessly.
REAL-WORLD CONNECTION
Think of a distributed cache that stores URL prefixes for routing requests. When a request arrives, the router walks the prefix tree once to decide which service handles it, rather than scanning every possible route—mirroring how a single DFS walks the board once to resolve many words.
During an interview, build the Trie first, then write a clean recursive helper that returns early on missing prefixes. Keep the visited matrix as a mutable boolean grid and flip cells in‑place to avoid extra copies—this pattern shows both algorithmic depth and engineering pragmatism.
COMPLEXITY AT A GLANCE
O(m·n·L) where L is the total number of characters in all wordsO(m·n + totalTrieNodes) – the board visited matrix plus the TrieCore Theory — Why This Approach?
The Grid Lexicon Verification problem is a classic application of depth‑first search (DFS) combined with backtracking. Each word is searched by starting from any cell that matches the first character and recursively exploring its four orthogonal neighbours while marking visited cells to enforce the "use‑once‑per‑word" rule. Naïve enumeration of all possible paths quickly explodes because the branching factor is up to four and the depth equals the word length, leading to O(4^L) per start cell, which is infeasible for large grids (m×n) and long word lists. The optimal paradigm introduces a prefix‑tree (Trie) that aggregates all query words; a single DFS traversal of the board can simultaneously pursue multiple word candidates, pruning branches as soon as the current prefix is absent in the Trie. This reduces redundant work dramatically, turning the worst‑case time into O(m·n·L) where L is the total number of characters across all words, while keeping space linear in the Trie size plus the recursion stack.
Interview Questions on This Problem
Q1How would you modify the solution if diagonal moves were also allowed?
Extend the direction vectors to include the four diagonal offsets, increasing the branching factor to eight. The core backtracking logic remains unchanged, but you must ensure the visited‑cell marking still prevents reuse, and the time complexity becomes O(m·n·8^L) without a Trie, or O(m·n·L) with a Trie after pruning.
Q2Explain how you could parallelize the search for a massive word list on a distributed system.
Partition the word list into disjoint subsets, build a separate Trie for each subset, and assign each Trie to a worker node. Each node runs the same board‑DFS, emitting found words locally. Finally, a reducer aggregates results. Because the board is read‑only, there is no contention, and the approach scales linearly with the number of workers.
Q3What trade‑offs arise when you replace the recursive DFS with an explicit stack implementation?
An explicit stack eliminates the risk of stack overflow on very deep recursions and gives finer control over memory usage, but it adds boilerplate for managing state (position, index in word, visited mask). The asymptotic time and space remain the same; however, iterative code can be slightly faster due to reduced function‑call overhead.
Examples
Input
{"grid":[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"words":["ABCCED","SEE","ABCB"]}Output
[true,true,false]
Explanation: Step-by-step: for the first word 'ABCCED', we start from 'A' and move right to 'B', then down to 'C', then right to 'C', then down to 'E', and finally right to 'D'. This forms the word 'ABCCED'. For the second word 'SEE', we start from 'S' and move right to 'E', then down to 'E'. This forms the word 'SEE'. For the third word 'ABCB', we start from 'A' and move right to 'B', then down to 'B', but there is no 'C' below 'B', so we cannot form the word 'ABCB'.
Input
{"grid":[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"words":["SEE","ABCB","AC"]}Output
[true,false,true]
Explanation: Step-by-step: for the first word 'SEE', we start from 'S' and move right to 'E', then down to 'E'. This forms the word 'SEE'. For the second word 'ABCB', we start from 'A' and move right to 'B', then down to 'B', but there is no 'C' below 'B', so we cannot form the word 'ABCB'. For the third word 'AC', we start from 'A' and move down to 'C'. This forms the word 'AC'.
Constraints
- The grid size can be up to 10x10.
- The number of words to find can be up to 10.
- Each word length can be up to 5 characters.
- Only English alphabets are used in the grid.
Optimal Approach & Strategy
Build a Trie of all words, then run a single DFS from each board cell, walking the Trie in lockstep and backtracking when the current path isn’t a prefix of any word. This shares work across words and prunes dead branches early.
Brute Force Approach
For each word, start a DFS from every cell that matches its first character and explore all four directions recursively, marking visited cells. This naïve method repeats the same prefix work for many words, leading to exponential time.
Verified Code Solutions
function exist(board, word) {
if (!board.length || !word.length) return false;
const rows = board.length, cols = board[0].length;
const visited = Array(rows).fill(0).map(() => Array(cols).fill(false));
function dfs(r, c, index) {
if (index === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || board[r][c] !== word[index]) return false;
visited[r][c] = true;
const res = dfs(r + 1, c, index + 1) || dfs(r - 1, c, index + 1) || dfs(r, c + 1, index + 1) || dfs(r, c - 1, index + 1);
visited[r][c] = false;
return res;
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || word.empty()) return false;
int rows = board.size(), cols = board[0].size();
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
function<bool(int, int, int)> dfs = [&](int r, int c, int index) {
if (index == word.size()) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || board[r][c] != word[index]) return false;
visited[r][c] = true;
bool res = dfs(r + 1, c, index + 1) || dfs(r - 1, c, index + 1) || dfs(r, c + 1, index + 1) || dfs(r, c - 1, index + 1);
visited[r][c] = false;
return res;
};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}public boolean exist(char[][] board, String word) {
if (board == null || word == null || board.length == 0 || word.length() == 0) return false;
int rows = board.length, cols = board[0].length;
boolean[][] visited = new boolean[rows][cols];
public boolean dfs(int r, int c, int index) {
if (index == word.length()) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || board[r][c] != word.charAt(index)) return false;
visited[r][c] = true;
boolean res = dfs(r + 1, c, index + 1) || dfs(r - 1, c, index + 1) || dfs(r, c + 1, index + 1) || dfs(r, c - 1, index + 1);
visited[r][c] = false;
return res;
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}def exist(board, word):
if not board or not word: return False
rows, cols = len(board), len(board[0])
visited = [[False]*cols for _ in range(rows)]
def dfs(r, c, index):
if index == len(word): return True
if r < 0 or r >= rows or c < 0 or c >= cols or visited[r][c] or board[r][c] != word[index]: return False
visited[r][c] = True
res = dfs(r + 1, c, index + 1) or dfs(r - 1, c, index + 1) or dfs(r, c + 1, index + 1) or dfs(r, c - 1, index + 1)
visited[r][c] = False
return res
for i in range(rows):
for j in range(cols):
if dfs(i, j, 0): return True
return Falsefunction exist(board, word) {
if (!board.length || !word.length) return false;
const rows = board.length, cols = board[0].length;
const visited = Array(rows).fill(0).map(() => Array(cols).fill(false));
function dfs(r, c, index) {
if (index === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || board[r][c] !== word[index]) return false;
visited[r][c] = true;
const res = dfs(r + 1, c, index + 1) || dfs(r - 1, c, index + 1) || dfs(r, c + 1, index + 1) || dfs(r, c - 1, index + 1);
visited[r][c] = false;
return res;
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.