Implement gridFindWord(grid, word) — given a 2D grid of single-character cells and a target word, return true if the word can be spelled by tracing a path through adjacent cells, and false otherwise. This is the core check behind a word-search puzzle: starting from some cell, each next letter must sit in a cell directly above, below, left, or right of the current one (not diagonally), and you may not step on the same cell twice within a single path.
// grid: string[][] — a rectangular grid; each cell is a one-character string.
// word: string — the target sequence of characters to spell.
// returns: boolean — true iff `word` can be traced along a path of
// 4-directionally adjacent cells, each used at most once.
function gridFindWord(grid: string[][], word: string): boolean;// "ABCCED" weaves down and across the board; the two C's land on two
// different cells, so the path is valid.
const grid = [
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E'],
];
gridFindWord(grid, 'ABCCED'); // → true// "ABCB" would need the single B at (0,1) twice. A cell can't be reused
// within one path, so there is no valid trace.
const grid = [
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E'],
];
gridFindWord(grid, 'ABCB'); // → false'aa' is impossible on a grid that holds a single 'a'.'A' and 'a' are different letters; gridFindWord([['A']], 'a') is false.true or false, not a truthy/falsy value like undefined or a cell.false. A word with more characters than the grid has cells can never fit without reuse, so it returns false too.word in, one boolean out.You'll search a grid of letters for a single target word, tracing a path between adjacent cells and never stepping on the same cell twice — depth-first search with backtracking.
This is the classic newspaper word-search puzzle, narrowed to one word. You're handed a grid of letters and a word, and you ask: can I put my pen on some cell, then slide it up, down, left, or right one cell at a time, spelling the word as I go, without ever crossing a cell I've already used? If yes, return true; if no path works, return false. The catch that makes it more than a string scan is that the same letter can appear in many cells, so finding the first letter somewhere isn't enough — you have to find a first letter that leads to a second that leads to a third, all the way to the end.
The whole solution is one idea: depth-first search with backtracking. From a starting cell, try to extend the word one letter at a time. Standing on a cell, you "claim" it so the rest of this path can't reuse it, then you recurse into each neighbour that could hold the next letter. If some neighbour leads to a complete spelling, you're done. If every neighbour fails, you "un-claim" the cell — restore it exactly as it was — and report failure up to the caller, who will try its own other neighbours. That claim-then-restore dance is backtracking, and it's what lets a cell be part of one attempted path and then freed for a different attempt.
The only movement rule is adjacency, and here it is 4-directional — up, down, left, right. Diagonals do not count. A letter that only touches the current cell at a corner is unreachable.
The instinct is right — start where the first letter matches, then walk outward matching the next letter. The first version usually gets the recursion going but forgets to un-mark a cell after a failed branch:
function gridFindWordNaive(grid, word) {
const rows = grid.length;
const cols = rows > 0 ? grid[0].length : 0;
function dfs(r, c, idx) {
if (grid[r][c] !== word[idx]) return false; // wrong letter here
if (idx === word.length - 1) return true; // matched the last char
grid[r][c] = null; // mark as used so we don't step back onto it
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dr, dc] of dirs) {
const nr = r + dr;
const nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (dfs(nr, nc, idx + 1)) return true; // found it — bubble success up
}
return false; // no neighbour worked — but we never restored grid[r][c]!
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}This finds plenty of words, but it quietly corrupts the grid. The line grid[r][c] = null marks a cell used, and there is no matching line to set it back. So once a DFS attempt touches a cell, that cell is null forever — even after the attempt fails and we move on to a different starting cell. A later path that genuinely needs that cell sees null instead of its letter and skips it, so we report false for words that are actually spellable. The marking is half-right; the restoring is missing.
The fix is one extra line: remember the cell's letter before blanking it, and write it back the moment this cell's exploration ends — whether the branch succeeded or failed.
function gridFindWord(grid, word) {
const rows = grid.length;
const cols = rows > 0 ? grid[0].length : 0;
// An empty word needs no cells; an empty grid offers none. Decide both up
// front so the search below can assume a non-empty word on a real grid.
if (word.length === 0) return true;
if (rows === 0 || cols === 0) return false;
// 4-directional steps: up, down, left, right. No diagonals.
const DIRS = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
];
// Can we spell word[idx..] starting on cell (r, c)?
function dfs(r, c, idx) {
// This cell must hold the letter we currently need.
if (grid[r][c] !== word[idx]) return false;
// It does — and if it's the LAST letter, the whole word is placed. Done.
if (idx === word.length - 1) return true;
// Claim the cell: blank it so deeper recursion can't step back onto it.
// `saved` lets us put the exact letter back on the way out.
const saved = grid[r][c];
grid[r][c] = null;
for (const [dr, dc] of DIRS) {
const nr = r + dr;
const nc = c + dc;
// Skip neighbours that fall off the grid. A blanked (null) cell simply
// fails its letter check below, so no separate "visited" test is needed.
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (dfs(nr, nc, idx + 1)) {
grid[r][c] = saved; // restore before bubbling success up
return true;
}
}
grid[r][c] = saved; // restore on the way back up — this is the backtrack
return false;
}
// Try every cell as a starting point; the word may begin anywhere.
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}
module.exports = { gridFindWord };Each non-obvious choice earns its place:
Marking by mutating the grid, not a separate visited set. Setting grid[r][c] = null does double duty: it records "this cell is on the current path" and guarantees the cell fails its own letter check (grid[r][c] !== word[idx]) if recursion tries to revisit it. Because null can never equal any one-character word[idx], the in-bounds neighbour loop needs no extra "is this cell used?" test — the letter check already rejects it. (A Set of visited coordinates works too; mutate-and-restore is just less bookkeeping.)
saved plus the restore line is the backtracking. Before recursing, we stash the real letter in saved and blank the cell. When this cell's exploration finishes — success or failure — we write saved back. That restore is what makes the same cell available to a different path later: the "used once" rule is meant to apply within one word's trace, not to permanently consume cells across the whole search.
The base case returns on the last letter, before recursing further. if (idx === word.length - 1) return true fires when the current cell holds the final character. There's no next letter to place, so the word is complete. Checking this before the marking step means a one-letter word like 'a' succeeds the instant it lands on a matching cell, without ever blanking anything.
Restore on the success path too. It's easy to write the restore only at the bottom (the failure path) and forget the early return true. Leaving it off the success branch wouldn't break the boolean answer — we're about to return true anyway — but it would leave the grid permanently mutated, breaking the "don't corrupt the input" contract. Restoring on both exits keeps the grid pristine no matter how the search ends.
Empty-grid and empty-word guards up front. rows === 0 || cols === 0 catches both [] and [[]] before any indexing, so the loops never touch an undefined row. The word.length === 0 guard returns true because the empty string is trivially "spellable" with a path of zero cells — though in practice callers don't pass it.
Trace gridFindWord(grid, 'ABCCED') on the board
A B C E
S F C S
A D E E
The outer loops hand starting cells to dfs(r, c, 0). Only (0,0) and (2,0) hold 'A', the first letter. The sweep reaches (0,0) first, so follow that one.
dfs(0,0, 0) grid[0][0]='A' === word[0]='A' not last char
saved='A', grid[0][0]=null claim (0,0)
neighbour (1,0)='S' !== word[1]='B' dfs returns false
neighbour (0,1)='B' === word[1]='B' descend
dfs(0,1, 1) not last char; saved='B', grid[0][1]=null
neighbour (0,2)='C' === word[2]='C' descend
dfs(0,2, 2) not last char; saved='C', grid[0][2]=null
neighbour (1,2)='C' === word[3]='C' descend (the 2nd C, a new cell)
dfs(1,2, 3) not last char; saved='C', grid[1][2]=null
neighbour (2,2)='E' === word[4]='E' descend
dfs(2,2, 4) not last char; saved='E', grid[2][2]=null
neighbour (2,1)='D' === word[5]='D' descend
dfs(2,1, 5) idx === word.length-1 → return true
restore grid[2][2]='E'; return true
restore grid[1][2]='C'; return true
restore grid[0][2]='C'; return true
restore grid[0][1]='B'; return true
restore grid[0][0]='A'; return true
gridFindWord → true
The interesting hop is at index 3. We've just spelled A → B → C ending on cell (0,2), and now we need another C. Cell (0,2) is itself a C, but it's currently null (we claimed it), so it can't be reused. The neighbour (1,2) is a different C, so the path continues there. That's the whole point of two same-letter cells: backtracking keeps them distinct. As the true bubbles up, every restore line fires in reverse order, so the grid ends exactly as it began — A B C E / S F C S / A D E E.
To see why the restore matters, picture a search that took a wrong turn first. Suppose from some cell DFS tried a neighbour that dead-ended a few letters in. Every cell that wrong branch claimed gets restored as the failed calls unwind, so when the parent tries its next neighbour, the board is back to full — those cells are available again for the new attempt.
grid[r][c] but never write it back, the first DFS attempt to touch a cell consumes it permanently. A word that's genuinely spellable through that cell — but only reachable from a later starting cell — then reports false, because by the time you start there the cell is still null. Pair every grid[r][c] = null with a grid[r][c] = saved before the function returns, on both the success and failure exits.word[0] in the grid is not enough; you have to find an occurrence of word[0] from which the rest of the word can be traced. That's why the outer loop tries every matching start and the recursion can fail and move on — 'abc' can have a, b, and c all present yet no connected path between them.DIRS list includes the diagonals ([-1,-1], [1,1], etc.), 'ab' on [['a','x'],['x','b']] — where b sits diagonally from a — is wrongly reported as true. List exactly the four orthogonal offsets and nothing else.null letter check that enforces it) and 'aa' becomes true on a grid with a single 'a': DFS steps from the a cell onto itself. The mark-and-restore is precisely what forbids a cell appearing twice in one trace.nr >= rows and nc >= cols, not >. Rows are indexed 0…rows-1; with >, an index equal to rows slips through and grid[rows] is undefined, which throws the moment you read grid[rows][nc]. Guard both the low edge (< 0) and the high edge (>= rows / >= cols).return dfs(...) from a branch that can yield undefined (a missing return), callers comparing === true will be surprised. Make sure every path returns an explicit true or false; the outer function's final return false is the catch-all when no starting cell works.[r, c] cells as you descend and return that array on success (and null on failure). The change is small: thread an accumulator through dfs, push the current cell before recursing, and pop it next to the restore line — the path mirrors the same claim/release rhythm as the grid mutation.cat, car, care all retrace c → a). Folding the dictionary into a trie and walking the grid against the tree once is the standard speedup — that's exactly the sibling problem, Find Words in Grid, which returns every formable word.visited Set of r * cols + c indices (add on entry, delete on backtrack) to keep the input strictly read-only throughout.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Implement gridFindWord(grid, word) — given a 2D grid of single-character cells and a target word, return true if the word can be spelled by tracing a path through adjacent cells, and false otherwise. This is the core check behind a word-search puzzle: starting from some cell, each next letter must sit in a cell directly above, below, left, or right of the current one (not diagonally), and you may not step on the same cell twice within a single path.
// grid: string[][] — a rectangular grid; each cell is a one-character string.
// word: string — the target sequence of characters to spell.
// returns: boolean — true iff `word` can be traced along a path of
// 4-directionally adjacent cells, each used at most once.
function gridFindWord(grid: string[][], word: string): boolean;// "ABCCED" weaves down and across the board; the two C's land on two
// different cells, so the path is valid.
const grid = [
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E'],
];
gridFindWord(grid, 'ABCCED'); // → true// "ABCB" would need the single B at (0,1) twice. A cell can't be reused
// within one path, so there is no valid trace.
const grid = [
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E'],
];
gridFindWord(grid, 'ABCB'); // → false'aa' is impossible on a grid that holds a single 'a'.'A' and 'a' are different letters; gridFindWord([['A']], 'a') is false.true or false, not a truthy/falsy value like undefined or a cell.false. A word with more characters than the grid has cells can never fit without reuse, so it returns false too.word in, one boolean out.You'll search a grid of letters for a single target word, tracing a path between adjacent cells and never stepping on the same cell twice — depth-first search with backtracking.
This is the classic newspaper word-search puzzle, narrowed to one word. You're handed a grid of letters and a word, and you ask: can I put my pen on some cell, then slide it up, down, left, or right one cell at a time, spelling the word as I go, without ever crossing a cell I've already used? If yes, return true; if no path works, return false. The catch that makes it more than a string scan is that the same letter can appear in many cells, so finding the first letter somewhere isn't enough — you have to find a first letter that leads to a second that leads to a third, all the way to the end.
The whole solution is one idea: depth-first search with backtracking. From a starting cell, try to extend the word one letter at a time. Standing on a cell, you "claim" it so the rest of this path can't reuse it, then you recurse into each neighbour that could hold the next letter. If some neighbour leads to a complete spelling, you're done. If every neighbour fails, you "un-claim" the cell — restore it exactly as it was — and report failure up to the caller, who will try its own other neighbours. That claim-then-restore dance is backtracking, and it's what lets a cell be part of one attempted path and then freed for a different attempt.
The only movement rule is adjacency, and here it is 4-directional — up, down, left, right. Diagonals do not count. A letter that only touches the current cell at a corner is unreachable.
The instinct is right — start where the first letter matches, then walk outward matching the next letter. The first version usually gets the recursion going but forgets to un-mark a cell after a failed branch:
function gridFindWordNaive(grid, word) {
const rows = grid.length;
const cols = rows > 0 ? grid[0].length : 0;
function dfs(r, c, idx) {
if (grid[r][c] !== word[idx]) return false; // wrong letter here
if (idx === word.length - 1) return true; // matched the last char
grid[r][c] = null; // mark as used so we don't step back onto it
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dr, dc] of dirs) {
const nr = r + dr;
const nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (dfs(nr, nc, idx + 1)) return true; // found it — bubble success up
}
return false; // no neighbour worked — but we never restored grid[r][c]!
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}This finds plenty of words, but it quietly corrupts the grid. The line grid[r][c] = null marks a cell used, and there is no matching line to set it back. So once a DFS attempt touches a cell, that cell is null forever — even after the attempt fails and we move on to a different starting cell. A later path that genuinely needs that cell sees null instead of its letter and skips it, so we report false for words that are actually spellable. The marking is half-right; the restoring is missing.
The fix is one extra line: remember the cell's letter before blanking it, and write it back the moment this cell's exploration ends — whether the branch succeeded or failed.
function gridFindWord(grid, word) {
const rows = grid.length;
const cols = rows > 0 ? grid[0].length : 0;
// An empty word needs no cells; an empty grid offers none. Decide both up
// front so the search below can assume a non-empty word on a real grid.
if (word.length === 0) return true;
if (rows === 0 || cols === 0) return false;
// 4-directional steps: up, down, left, right. No diagonals.
const DIRS = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
];
// Can we spell word[idx..] starting on cell (r, c)?
function dfs(r, c, idx) {
// This cell must hold the letter we currently need.
if (grid[r][c] !== word[idx]) return false;
// It does — and if it's the LAST letter, the whole word is placed. Done.
if (idx === word.length - 1) return true;
// Claim the cell: blank it so deeper recursion can't step back onto it.
// `saved` lets us put the exact letter back on the way out.
const saved = grid[r][c];
grid[r][c] = null;
for (const [dr, dc] of DIRS) {
const nr = r + dr;
const nc = c + dc;
// Skip neighbours that fall off the grid. A blanked (null) cell simply
// fails its letter check below, so no separate "visited" test is needed.
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (dfs(nr, nc, idx + 1)) {
grid[r][c] = saved; // restore before bubbling success up
return true;
}
}
grid[r][c] = saved; // restore on the way back up — this is the backtrack
return false;
}
// Try every cell as a starting point; the word may begin anywhere.
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}
module.exports = { gridFindWord };Each non-obvious choice earns its place:
Marking by mutating the grid, not a separate visited set. Setting grid[r][c] = null does double duty: it records "this cell is on the current path" and guarantees the cell fails its own letter check (grid[r][c] !== word[idx]) if recursion tries to revisit it. Because null can never equal any one-character word[idx], the in-bounds neighbour loop needs no extra "is this cell used?" test — the letter check already rejects it. (A Set of visited coordinates works too; mutate-and-restore is just less bookkeeping.)
saved plus the restore line is the backtracking. Before recursing, we stash the real letter in saved and blank the cell. When this cell's exploration finishes — success or failure — we write saved back. That restore is what makes the same cell available to a different path later: the "used once" rule is meant to apply within one word's trace, not to permanently consume cells across the whole search.
The base case returns on the last letter, before recursing further. if (idx === word.length - 1) return true fires when the current cell holds the final character. There's no next letter to place, so the word is complete. Checking this before the marking step means a one-letter word like 'a' succeeds the instant it lands on a matching cell, without ever blanking anything.
Restore on the success path too. It's easy to write the restore only at the bottom (the failure path) and forget the early return true. Leaving it off the success branch wouldn't break the boolean answer — we're about to return true anyway — but it would leave the grid permanently mutated, breaking the "don't corrupt the input" contract. Restoring on both exits keeps the grid pristine no matter how the search ends.
Empty-grid and empty-word guards up front. rows === 0 || cols === 0 catches both [] and [[]] before any indexing, so the loops never touch an undefined row. The word.length === 0 guard returns true because the empty string is trivially "spellable" with a path of zero cells — though in practice callers don't pass it.
Trace gridFindWord(grid, 'ABCCED') on the board
A B C E
S F C S
A D E E
The outer loops hand starting cells to dfs(r, c, 0). Only (0,0) and (2,0) hold 'A', the first letter. The sweep reaches (0,0) first, so follow that one.
dfs(0,0, 0) grid[0][0]='A' === word[0]='A' not last char
saved='A', grid[0][0]=null claim (0,0)
neighbour (1,0)='S' !== word[1]='B' dfs returns false
neighbour (0,1)='B' === word[1]='B' descend
dfs(0,1, 1) not last char; saved='B', grid[0][1]=null
neighbour (0,2)='C' === word[2]='C' descend
dfs(0,2, 2) not last char; saved='C', grid[0][2]=null
neighbour (1,2)='C' === word[3]='C' descend (the 2nd C, a new cell)
dfs(1,2, 3) not last char; saved='C', grid[1][2]=null
neighbour (2,2)='E' === word[4]='E' descend
dfs(2,2, 4) not last char; saved='E', grid[2][2]=null
neighbour (2,1)='D' === word[5]='D' descend
dfs(2,1, 5) idx === word.length-1 → return true
restore grid[2][2]='E'; return true
restore grid[1][2]='C'; return true
restore grid[0][2]='C'; return true
restore grid[0][1]='B'; return true
restore grid[0][0]='A'; return true
gridFindWord → true
The interesting hop is at index 3. We've just spelled A → B → C ending on cell (0,2), and now we need another C. Cell (0,2) is itself a C, but it's currently null (we claimed it), so it can't be reused. The neighbour (1,2) is a different C, so the path continues there. That's the whole point of two same-letter cells: backtracking keeps them distinct. As the true bubbles up, every restore line fires in reverse order, so the grid ends exactly as it began — A B C E / S F C S / A D E E.
To see why the restore matters, picture a search that took a wrong turn first. Suppose from some cell DFS tried a neighbour that dead-ended a few letters in. Every cell that wrong branch claimed gets restored as the failed calls unwind, so when the parent tries its next neighbour, the board is back to full — those cells are available again for the new attempt.
grid[r][c] but never write it back, the first DFS attempt to touch a cell consumes it permanently. A word that's genuinely spellable through that cell — but only reachable from a later starting cell — then reports false, because by the time you start there the cell is still null. Pair every grid[r][c] = null with a grid[r][c] = saved before the function returns, on both the success and failure exits.word[0] in the grid is not enough; you have to find an occurrence of word[0] from which the rest of the word can be traced. That's why the outer loop tries every matching start and the recursion can fail and move on — 'abc' can have a, b, and c all present yet no connected path between them.DIRS list includes the diagonals ([-1,-1], [1,1], etc.), 'ab' on [['a','x'],['x','b']] — where b sits diagonally from a — is wrongly reported as true. List exactly the four orthogonal offsets and nothing else.null letter check that enforces it) and 'aa' becomes true on a grid with a single 'a': DFS steps from the a cell onto itself. The mark-and-restore is precisely what forbids a cell appearing twice in one trace.nr >= rows and nc >= cols, not >. Rows are indexed 0…rows-1; with >, an index equal to rows slips through and grid[rows] is undefined, which throws the moment you read grid[rows][nc]. Guard both the low edge (< 0) and the high edge (>= rows / >= cols).return dfs(...) from a branch that can yield undefined (a missing return), callers comparing === true will be surprised. Make sure every path returns an explicit true or false; the outer function's final return false is the catch-all when no starting cell works.[r, c] cells as you descend and return that array on success (and null on failure). The change is small: thread an accumulator through dfs, push the current cell before recursing, and pop it next to the restore line — the path mirrors the same claim/release rhythm as the grid mutation.cat, car, care all retrace c → a). Folding the dictionary into a trie and walking the grid against the tree once is the standard speedup — that's exactly the sibling problem, Find Words in Grid, which returns every formable word.visited Set of r * cols + c indices (add on entry, delete on backtrack) to keep the input strictly read-only throughout.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.