JavaScript
class Solution {
// Solution using DFS and Set
exist(board, word) {
const ROWS = board.length;
const COLS = board[0].length;
const path = new Set();
const dfs = (r, c, i) => {
if (i === word.length) return true;
if (r < 0 || c < 0 || r >= ROWS || c >= COLS ||
board[r][c] !== word[i] || path.has(`${r},${c}`)) {
return false;
}
path.add(`${r},${c}`);
const res = dfs(r + 1, c, i + 1) ||
dfs(r - 1, c, i + 1) ||
dfs(r, c + 1, i + 1) ||
dfs(r, c - 1, i + 1);
path.delete(`${r},${c}`);
return res;
};
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}
// Time complexity: O(N * M * 4^L)
// Space complexity: O(L)
// Alternative solution with board modification
exist2(board, word) {
const ROWS = board.length;
const COLS = board[0].length;
const dfs = (r, c, i) => {
if (i === word.length) return true;
if (r < 0 || c < 0 || r >= ROWS || c >= COLS || board[r][c] !== word[i]) {
return false;
}
const temp = board[r][c];
board[r][c] = '#'; // mark as visited
const res = dfs(r + 1, c, i + 1) ||
dfs(r - 1, c, i + 1) ||
dfs(r, c + 1, i + 1) ||
dfs(r, c - 1, i + 1);
board[r][c] = temp; // restore original value
return res;
};
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}
// Time complexity: O(N * M * 4^L)
// Space complexity: O(1)
}
Java
class Solution {
// Solution using DFS and visited cells
public boolean exist(char[][] board, String word) {
int ROWS = board.length;
int COLS = board[0].length;
for(int i = 0; i < ROWS; i++) {
for(int j = 0; j < COLS; j++) {
if(board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, int row, int col, int count, String word) {
if(count == word.length()) return true;
if(row < 0 || col < 0 || row >= board.length || col >= board[0].length ||
board[row][col] != word.charAt(count)) {
return false;
}
char temp = board[row][col];
board[row][col] = '*';
boolean found = dfs(board, row + 1, col, count + 1, word) ||
dfs(board, row - 1, col, count + 1, word) ||
dfs(board, row, col + 1, count + 1, word) ||
dfs(board, row, col - 1, count + 1, word);
board[row][col] = temp;
return found;
}
// Time complexity: O(N * M * 4^L)
// Space complexity: O(L)
}
Python
class Solution:
# Solution using DFS and set
def exist(self, board: List[List[str]], word: str) -> bool:
ROWS, COLS = len(board), len(board[0])
path = set()
def dfs(r, c, i):
if i == len(word):
return True
if (r < 0 or c < 0 or
r >= ROWS or c >= COLS or
word[i] != board[r][c] or
(r, c) in path):
return False
path.add((r, c))
res = (dfs(r + 1, c, i + 1) or
dfs(r - 1, c, i + 1) or
dfs(r, c + 1, i + 1) or
dfs(r, c - 1, i + 1))
path.remove((r, c))
return res
for r in range(ROWS):
for c in range(COLS):
if dfs(r, c, 0): return True
return False
# Time complexity: O(N * M * 4^L)
# Space complexity: O(L)
# Alternative solution using board modification
def exist2(self, board: List[List[str]], word: str) -> bool:
ROWS, COLS = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if (r < 0 or c < 0 or
r >= ROWS or c >= COLS or
board[r][c] != word[i]):
return False
temp = board[r][c]
board[r][c] = '#' # mark as visited
res = (dfs(r + 1, c, i + 1) or
dfs(r - 1, c, i + 1) or
dfs(r, c + 1, i + 1) or
dfs(r, c - 1, i + 1))
board[r][c] = temp # restore original value
return res
for r in range(ROWS):
for c in range(COLS):
if dfs(r, c, 0): return True
return False
# Time complexity: O(N * M * 4^L)
# Space complexity: O(1)