🎨Now live: Try our Free AI Image Generation Feature

Description
The problem is to determine if a given word can be found in a 2D board of characters. You can only move horizontally or vertically from a cell and you cannot revisit the same cell within a single path. The word must be constructed sequentially from the board's characters.
For example, given a board
:
[ ['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E'] ]
and a word
"ABCCED", the method should return true
because the word can be constructed as follows: A -> B -> C -> C -> E -> D
.
Intuition
The task is to explore the board to check if the word can be constructed by traversing adjacent cells. The problem can be approached using depth-first search (DFS) with backtracking:
- Start from each cell in the board.
- Recursively search for the next character in the word.
- Mark cells as visited to avoid reusing them in the current path.
- Backtrack to explore other potential paths if needed.
Approach
- Initialization:
- Check if the board or word is empty. If so, return
False
. - Initialize avisited
matrix to keep track of which cells have been visited. - Recursive Function (
backtrack
): - Base Case: If the index equals the length of the word, returnTrue
. - Boundary Check: If the current cell is out of bounds, already visited, or does not match the current character in the word, returnFalse
. - Mark as Visited: Mark the current cell as visited. - Explore Directions: Recursively explore all four possible directions (down, up, right, left) from the current cell. - Backtrack: After exploring, unmark the cell to allow other potential paths. - Main Search Loop: - Iterate through each cell in the board and start the backtracking process if the cell matches the first character of the word.
- Return Result:
- Return
True
if the word is found; otherwise, returnFalse
.
Complexity
Time Complexity:
O(M * N * 4^L)
- Where
M
andN
are the dimensions of the board, andL
is the length of the word. - In the worst case, each cell is visited multiple times, and there are up to
4^L
possible paths to explore due to the four directions.
Space Complexity:
O(M * N)
- Space complexity is determined by the space used for the
visited
matrix and the recursion stack. - The
visited
matrix has a size ofM * N
, and the maximum depth of recursion isL
, which in the worst case can be proportional to the board size.
Code
C++
class Solution {
public:
bool exist(vector>& board, string word) {
if (board.empty() || board[0].empty()) return false;
vector> visited(board.size(), vector(board[0].size(), false));
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
if (backtrack(board, word, i, j, 0, visited)) {
return true;
}
}
}
return false;
}
private:
bool backtrack(vector>& board, const string& word, int i, int j, int k, vector>& visited) {
if (k == word.length()) return true;
if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j] || board[i][j] != word[k]) {
return false;
}
visited[i][j] = true;
bool found = backtrack(board, word, i + 1, j, k + 1, visited) ||
backtrack(board, word, i - 1, j, k + 1, visited) ||
backtrack(board, word, i, j + 1, k + 1, visited) ||
backtrack(board, word, i, j - 1, k + 1, visited);
visited[i][j] = false;
return found;
}
};
Python
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not board or not board[0]:
return False
rows, cols = len(board), len(board[0])
visited = [[False] * cols for _ in range(rows)]
def backtrack(r, c, index):
if index == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or visited[r][c] or board[r][c] != word[index]:
return False
visited[r][c] = True
# Explore all four directions: down, up, right, left
found = (backtrack(r + 1, c, index + 1) or
backtrack(r - 1, c, index + 1) or
backtrack(r, c + 1, index + 1) or
backtrack(r, c - 1, index + 1))
visited[r][c] = False
return found
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return False
Java
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (backtrack(board, word, i, j, 0, visited)) {
return true;
}
}
}
return false;
}
private boolean backtrack(char[][] board, String word, int i, int j, int k, boolean[][] visited) {
if (k == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(k)) {
return false;
}
visited[i][j] = true;
boolean found = backtrack(board, word, i + 1, j, k + 1, visited) ||
backtrack(board, word, i - 1, j, k + 1, visited) ||
backtrack(board, word, i, j + 1, k + 1, visited) ||
backtrack(board, word, i, j - 1, k + 1, visited);
visited[i][j] = false;
return found;
}
}
JavaScript
var exist = function (board, word)
{
const visited = Array.from(Array(board.length), () => Array(board[0].length).fill(false));
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (backtrack(board, word, i, j, 0, visited))
return true;
}
}
return false;
};
function backtrack(board, word, i, j, k, visited)
{
if (k === word.length)
return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] !== word.charAt(k))
return false;
visited[i][j] = true;
if (backtrack(board, word, i + 1, j, k + 1, visited) ||
backtrack(board, word, i - 1, j, k + 1, visited) ||
backtrack(board, word, i, j + 1, k + 1, visited) ||
backtrack(board, word, i, j - 1, k + 1, visited))
return true;
visited[i][j] = false;
return false;
}