Intermediate Level
Implement the wordSearchGridExists method that checks whether a word can be formed in the grid by adjacent cells.
The input contains a character grid board, its rows and cols, and a string word.
Your task is to check whether the word can be formed by moving through adjacent cells in the grid. From a cell, you may move up, down, left, or right.
The same cell cannot be used more than once in the same word path. Return true if the word exists in the grid, otherwise return false.
Example 1
Input
board (char[][]) =
[[A,B,C,E],[S,F,C,S],[A,D,E,E]]rows (int) =
3cols (int) =
4word (string) =
ABCCEDReturns (boolean)
trueExample 2
Input
board (char[][]) =
[[A,B],[C,D]]rows (int) =
2cols (int) =
2word (string) =
ACReturns (boolean)
trueExample 3
Input
board (char[][]) =
[[A,B],[C,D]]rows (int) =
2cols (int) =
2word (string) =
ADReturns (boolean)
falseUse DFS with backtracking from every cell that could start the word.
At each step, check whether the current cell matches the current character of the word. If it matches, temporarily mark the cell as visited and try the four neighbouring cells for the next character.
If all characters are matched, the word exists. If a path fails, unmark the cell and try another path.
Pseudocode:
function wordSearchGridExists(board, rows, cols, word):
for row from 0 to rows - 1:
for col from 0 to cols - 1:
if dfs(row, col, 0) == true:
return true
return false
function dfs(row, col, index):
if index == length of word:
return true
if row or col is outside board:
return false
if board[row][col] != word[index]:
return false
save current character
mark board[row][col] as visited
found = dfs(row - 1, col, index + 1) OR
dfs(row + 1, col, index + 1) OR
dfs(row, col - 1, index + 1) OR
dfs(row, col + 1, index + 1)
restore current character
return foundReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run