Coding · Graphs and grids
Word Search, right and down moves only
- Reported in several places
- Medium
- SDE-2
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
You get a grid of letters, given as an array of equal-length strings, and a target word. Decide whether the word can be spelled by a path that starts at any cell and then repeatedly steps one cell right or one cell down, reading one letter per cell. For the grid ["ooo","ozz","eze"] and the word "ooze" the answer is true: start at the top middle o, step right to o, then down to z, then down to e. Moves left and up are not allowed. Assume a grid up to 100 by 100 and a word up to 100 letters.
Restated in our own words, not a quote from Atlassian or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: may the path start at any cell, or only the top-left? Is the word guaranteed to be non-empty? Are rows all the same length? Is matching case sensitive? Do I return only true or false, or the path as well? Does the word have to use each cell at most once (it always will here, since moves only go right or down)?
I would assume any starting cell, a non-empty word (false for an empty word or empty grid), exact letter matches, and a boolean result. I would also confirm the key difference from the classic puzzle: there you may move in four directions, so a path can wind back near itself.
Brute force
Say the obvious answer and why it is too slow.
Start a search from every cell, and at each step try both moves, right and down, without remembering anything. Every step branches in two, so a long run of matching letters costs up to 2^L paths. On a grid of all a's with the word "aaaa...ab", every path matches until the last letter and fails there, so the work is exponential in the word length. With L near 100 that cannot finish.
Many of those paths arrive at the same cell needing the same next letter, and the search repeats that sub-problem again and again. Remembering the failures should cut this down.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(m · n · 2^L)
- Time
- O(m · n · L)
- Space
- O(m · n · L)
The pattern is grid DFS with memoisation. Define search(row, col, index) as: can the word be finished if cell (row, col) is used for letter number index? It is true if that cell holds the letter, and either the word ends here or one of the two moves, right or down, continues the match.
The classic Word Search lets you walk in four directions without reusing a cell. That needs a visited mark and backtracking, because a path can turn back near itself, and there is no safe way to memoise since the visited set changes the answer. Here the situation is simpler. Every step raises row plus column by one, so a path can never return to a cell, and there is no visited set at all. The answer to search(row, col, index) depends only on those three numbers, not on how we got there. That is what makes memoisation valid.
Because the first success ends everything, I only store failures: the set of dead states (row, col, index). Before exploring a state, check the set; after both moves fail, add the state. The index is part of the key because one cell can serve different letter positions from different starting cells.
There are at most rows × cols × length states, each doing constant work apart from its two recursive calls, which are either a memo hit or a quick mismatch. That gives O(m · n · L) instead of 2^L. A path covers at most rows + cols - 1 cells, so a longer word is rejected at once. Out loud: "try right and down; remember every (cell, letter) pair that has already failed."
Walk it through
A dry run on the example, step by step.
| step | cell, k | need / have | result |
|---|---|---|---|
| 1 | (0,0) k=0 | o / o | match, go right |
| 2 | (0,1) k=1 | o / o | match, go right |
| 3 | (0,2) k=2 | z / o | mismatch |
| 4 | (1,1) k=2 | z / z | next two fail: dead |
| 5 | (1,0) k=1 | o / o | match, go right |
| 6 | (1,1) k=2 | dead already | memo hit, skip |
| 7 | (2,0) k=2 | z / e | mismatch; start dead |
| 8 | (0,1) k=0 | o / o | new start, go right |
| 9 | (0,2) k=1 | o / o | right is off, go down |
| 10 | (1,2),(2,2) | z / z, e / e | word complete: true |
Take the grid ["ooo","ozz","eze"] and the word "ooze", trying starts in row-major order. Start (0,0) matches o, then (0,1) matches o. From (0,1) the right move reaches (0,2), which holds o where z is needed, and the down move reaches (1,1) z, which matches. From (1,1) both moves need an e and find z, so (1,1) is recorded as dead for letter 2.
Back at (0,0), the down move reaches (1,0) o, whose right move hits the dead (1,1) state and is skipped, and whose down move finds e instead of z. So the start (0,0) fails. Start (0,1) matches o, (0,2) matches o, then down (1,2) is z and down (2,2) is e: the word is complete, so the answer is true. The trace lists these steps.
The code
Runnable JavaScript, checked against test cases.
function wordPathExists(grid, word) {
const rows = grid.length;
const cols = rows > 0 ? grid[0].length : 0;
if (rows === 0 || cols === 0 || word.length === 0) return false;
if (word.length > rows + cols - 1) return false;
const deadEnds = new Set();
const search = (row, col, index) => {
if (row >= rows || col >= cols || grid[row][col] !== word[index]) return false;
if (index === word.length - 1) return true;
const key = (row * cols + col) * word.length + index;
if (deadEnds.has(key)) return false;
if (search(row, col + 1, index + 1) || search(row + 1, col, index + 1)) return true;
deadEnds.add(key);
return false;
};
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
if (search(row, col, 0)) return true;
}
}
return false;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Empty grid or empty word: return false before searching.
- Word longer than a path can be: more than rows + cols - 1 letters is rejected immediately.
- One-letter word: true if any cell holds that letter.
- Wrong direction: "tac" in ["cat"] is false, because spelling it needs left moves that the classic puzzle would allow.
- Off the grid: the bounds check runs before the grid is indexed, so a move past the last row or column just fails.
- Single row or column: the problem reduces to a substring search.
- Repeating letters: grids of a's are the case where the memo matters.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it bottom-up with a table instead of recursion, and what is the space?
- How would the solution change if diagonal-down-right moves were also allowed?
- How would you return the path itself, not just true or false?
- What if the word may be several thousand letters long, and recursion depth becomes a concern?
Where candidates slip
The mistakes this problem punishes.
Common mistakes on this variant:
- Copying the classic four-direction solution, with a visited mark and left and up moves, which accepts paths this problem forbids.
- Searching only from the top-left cell instead of from every cell.
- Indexing the grid before checking the bounds.
- Leaving the letter index out of the memo key, so a cell that failed for one letter is wrongly dead for another.
- Recording a dead end before both moves have been tried.
- Off-by-one on the last letter: the word is complete when the matched index is length - 1.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.