Implement the wordSearchMatrixExists method that checks whether the word exists in the matrix path.
The input contains a character matrix board, its rows and cols, and a string word.
Your task is to check whether the word can be formed by starting from any cell and moving to adjacent cells one character at a time.
Only horizontal and vertical moves are allowed. The same cell should not be reused in one word path. For example, AB exists in [[A,B],[C,D]], but AD does not because it requires a diagonal move.
Example 1
[[A,B],[C,D]]22ABtrueExample 2
[[A,B],[C,D]]22ADfalseExample 3
[[A]]11AtrueTry to start the word from every cell that matches the first character.
From a matching cell, use backtracking to search the next character in the four possible directions: up, down, left, and right. Mark the current cell as visited before moving further so it is not used again in the same path.
If all characters are matched, return true. If every possible path fails, return false.
Pseudocode:
function wordSearchMatrixExists(board, rows, cols, word):
for i from 0 to rows - 1:
for j from 0 to cols - 1:
if search(i, j, 0) == true:
return true
return false
function search(row, col, index):
if index == length(word):
return true
if row is outside board or col is outside board:
return false
if board[row][col] != word[index]:
return false
temporarily mark board[row][col] as visited
found = search(row + 1, col, index + 1) OR
search(row - 1, col, index + 1) OR
search(row, col + 1, index + 1) OR
search(row, col - 1, index + 1)
restore board[row][col]
return found