Word Search
You are given a grid of letters, board, given as a list of strings of equal length (one string per row), and a string word. Return true if word can be formed by a path through the grid, and false otherwise.
A path starts at any cell, and each next letter comes from a cell directly above, below, to the left or to the right of the previous one. The same cell may not be used twice in one path.
Examples
The line traces ABCCED, starting at the dot.
Input board = ["ABCE", "SFCS", "ADEE"], word = "ABCCED"
Output true
The line traces SEE, starting at the dot.
Input board = ["ABCE", "SFCS", "ADEE"], word = "SEE"
Output true
Input board = ["ABCE", "SFCS", "ADEE"], word = "ABCB"
Output false
The path would have to use the B twice.
Constraints
- 1 <= number of rows, number of columns <= 6
- 1 <= word.length <= 15
- board and word contain only uppercase and lowercase English letters
Stuck? Take one hint at a time
Common mistakes
- Forgetting to unmark the cell after exploring, so a failed path leaves cells blocked for the next start.
- Not marking at all, so a path can reuse a cell (ABCB is wrongly accepted).
- Checking the letter only before the call, so the recursion accepts a cell without comparing it to word[k].
- Returning from the first neighbor instead of trying all four: only a true result should end the loop early.
- Checking the bounds after reading the cell, which throws an index error at the edge.
Questions an interviewer may ask next
- Return the path (the list of cells) instead of a yes or no.
- You must look up thousands of words in the same board. (Build a trie of the words and search the board once. This is Word Search II.)
- The word may use a cell more than once, but not twice in a row. How does the marking change?
- Also allow diagonal moves. How many directions are there now, and what happens to the worst case?
How often this is reported
Commonly reported across 7 of 25 tracked companies
7/25
Grade C: Reported in one source, or backed mainly by volume of reports. This reflects what candidates report, not a guarantee of what any company will ask.
board
["ABCE","SFCS","ADEE"]
word
"ABCCED"
Expected output
true
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.