## Word Search

• Time:O(mn4^{|\texttt{word}|})
• Space:O(4^{|\texttt{word}|})

## C++

``````class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board[0].size(); ++j)
if (dfs(board, word, i, j, 0))
return true;
return false;
}

private:
bool dfs(vector<vector<char>>& board, const string& word, int i, int j,
int s) {
if (i < 0 || i == board.size() || j < 0 || j == board[0].size())
return false;
if (board[i][j] != word[s] || board[i][j] == '*')
return false;
if (s == word.length() - 1)
return true;

const char cache = board[i][j];
board[i][j] = '*';
const bool isExist = dfs(board, word, i + 1, j, s + 1) ||
dfs(board, word, i - 1, j, s + 1) ||
dfs(board, word, i, j + 1, s + 1) ||
dfs(board, word, i, j - 1, s + 1);
board[i][j] = cache;

return isExist;
}
};
``````

## JAVA

``````class Solution {
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; ++i)
for (int j = 0; j < board[0].length; ++j)
if (dfs(board, word, i, j, 0))
return true;
return false;
}

private boolean dfs(char[][] board, String word, int i, int j, int s) {
if (i < 0 || i == board.length || j < 0 || j == board[0].length)
return false;
if (board[i][j] != word.charAt(s) || board[i][j] == '*')
return false;
if (s == word.length() - 1)
return true;

final char cache = board[i][j];
board[i][j] = '*';
final boolean isExist = dfs(board, word, i + 1, j, s + 1) ||
dfs(board, word, i - 1, j, s + 1) ||
dfs(board, word, i, j + 1, s + 1) ||
dfs(board, word, i, j - 1, s + 1);
board[i][j] = cache;

return isExist;
}
}
``````

## Python

``````class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m = len(board)
n = len(board[0])

def dfs(i: int, j: int, s: int) -> bool:
if i < 0 or i == m or j < 0 or j == n:
return False
if board[i][j] != word[s] or board[i][j] == '*':
return False
if s == len(word) - 1:
return True

cache = board[i][j]
board[i][j] = '*'
isExist = \
dfs(i + 1, j, s + 1) or \
dfs(i - 1, j, s + 1) or \
dfs(i, j + 1, s + 1) or \
dfs(i, j - 1, s + 1)
board[i][j] = cache

return isExist

return any(dfs(i, j, 0) for i in range(m) for j in range(n))
``````