Dare2Solve
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
.
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:
Initialization:
False
.visited
matrix to keep track of which cells have been visited.Recursive Function (backtrack
):
True
.False
.Main Search Loop:
Return Result:
True
if the word is found; otherwise, return False
.O(M * N * 4^L)
M
and N
are the dimensions of the board, and L
is the length of the word.4^L
possible paths to explore due to the four directions.O(M * N)
visited
matrix and the recursion stack.visited
matrix has a size of M * N
, and the maximum depth of recursion is L
, which in the worst case can be proportional to the board size.class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty()) return false;
vector<vector<bool>> visited(board.size(), vector<bool>(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<vector<char>>& board, const string& word, int i, int j, int k, vector<vector<bool>>& 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;
}
};
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
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;
}
}
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;
}