Word Search - Implementation

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

$O(m \cdot n \cdot 4^L)$ worst case where $L$ is word length. $O(L)$ space for recursion.