LeetCode 212 Word Search II - Implementation

Here's the solution:

function exist(board, word):
    for i in range(rows):
        for j in range(cols):
            if dfs(i, j, 0):
                return true
    return false

function dfs(i, j, k):
    if k == len(word): return true
    if outOfBounds or visited or board[i][j] != word[k]:
        return false
    mark visited
    found = dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
    unmark visited
    return found

$O(m \times n \times 4^L)$ time, $O(W \cdot L)$ space where $L$ is max word length, $W$ is word count.