Here is the implementation:
function exist(board, word):
for i from 0 to rows - 1:
for j from 0 to cols - 1:
if backtrack(i, j, 0):
return true
return false
function backtrack(i, j, index):
if index == word.length:
return true
if i < 0 or i >= rows or j < 0 or j >= cols:
return false
if board[i][j] != word[index]:
return false
temp = board[i][j]
board[i][j] = '#' // Mark visited
found = backtrack(i+1, j, index+1) or
backtrack(i-1, j, index+1) or
backtrack(i, j+1, index+1) or
backtrack(i, j-1, index+1)
board[i][j] = temp // Restore
return found
worst case where is word length. space for recursion.