#include <stdbool.h>
#include <string.h>
static const int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
static bool dfs(char **board, int rows, int cols, const char *word, int len,
int idx, int row, int col) {
char ch = word[idx];
if (ch != board[row][col])
return false;
if (idx == len - 1)
return true;
board[row][col] = '#';
for (int d = 0; d < 4; d++) {
int nr = row + dirs[d][0], nc = col + dirs[d][1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols)
continue;
if (dfs(board, rows, cols, word, len, idx + 1, nr, nc)) {
board[row][col] = ch; // restore before returning, so the board is unchanged
return true;
}
}
board[row][col] = ch;
return false;
}
bool exist(char **board, int boardSize, int *boardColSize, char *word) {
int len = strlen(word);
for (int r = 0; r < boardSize; r++)
for (int c = 0; c < boardColSize[0]; c++)
if (dfs(board, boardSize, boardColSize[0], word, len, 0, r, c))
return true;
return false;
}
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
bool exist(vector<vector<char>> &board, const string &word) {
for (int r = 0; r < (int)board.size(); r++)
for (int c = 0; c < (int)board[0].size(); c++)
if (dfs(board, word, 0, r, c))
return true;
return false;
}
bool dfs(vector<vector<char>> &board, const string &word, int idx, int row,
int col) {
int constexpr dict[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char ch = word[idx];
if (ch != board[row][col])
return false;
if (idx == word.size() - 1)
return true;
board[row][col] = '#';
for (auto [dr, dc] : dict) {
int nr = row + dr, nc = col + dc;
if (nr < 0 || nr >= board.size() || nc < 0 || nc >= board[0].size())
continue;
if (dfs(board, word, idx + 1, nr, nc)) {
board[row][col] = ch; // restore before returning, so the board is unchanged
return true;
}
}
board[row][col] = ch;
return false;
}
};
package backtracking
var dirs = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
func exist(board [][]byte, word string) bool {
var dfs func(idx, row, col int) bool
dfs = func(idx, row, col int) bool {
ch := word[idx]
if ch != board[row][col] {
return false
}
if idx == len(word)-1 {
return true
}
board[row][col] = '#'
for _, d := range dirs {
nr, nc := row+d[0], col+d[1]
if nr < 0 || nr >= len(board) || nc < 0 || nc >= len(board[0]) {
continue
}
if dfs(idx+1, nr, nc) {
board[row][col] = ch // restore before returning, so the board is unchanged
return true
}
}
board[row][col] = ch
return false
}
for r := range board {
for c := range board[0] {
if dfs(0, r, c) {
return true
}
}
}
return false
}
class Solution {
private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public boolean exist(char[][] board, String word) {
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
if (dfs(board, word, 0, r, c)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int idx, int row, int col) {
char ch = word.charAt(idx);
if (ch != board[row][col]) {
return false;
}
if (idx == word.length() - 1) {
return true;
}
board[row][col] = '#';
for (int[] d : DIRS) {
int nr = row + d[0], nc = col + d[1];
if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) {
continue;
}
if (dfs(board, word, idx + 1, nr, nc)) {
board[row][col] = ch; // restore before returning, so the board is unchanged
return true;
}
}
board[row][col] = ch;
return false;
}
}
const DIRS = [
[1, 0],
[0, 1],
[-1, 0],
[0, -1],
];
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function (board, word) {
const dfs = (idx, row, col) => {
const ch = word[idx];
if (ch !== board[row][col]) return false;
if (idx === word.length - 1) return true;
board[row][col] = "#";
for (const [dr, dc] of DIRS) {
const nr = row + dr,
nc = col + dc;
if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length)
continue;
if (dfs(idx + 1, nr, nc)) {
board[row][col] = ch; // restore before returning, so the board is unchanged
return true;
}
}
board[row][col] = ch;
return false;
};
for (let r = 0; r < board.length; r++)
for (let c = 0; c < board[0].length; c++) if (dfs(0, r, c)) return true;
return false;
};
from typing import List
DIRS = ((1, 0), (0, 1), (-1, 0), (0, -1))
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def dfs(idx: int, row: int, col: int) -> bool:
ch = word[idx]
if ch != board[row][col]:
return False
if idx == len(word) - 1:
return True
board[row][col] = "#"
for dr, dc in DIRS:
nr, nc = row + dr, col + dc
if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
continue
if dfs(idx + 1, nr, nc):
board[row][col] = ch # restore before returning, so the board is unchanged
return True
board[row][col] = ch
return False
return any(dfs(0, r, c) for r in range(rows) for c in range(cols))
const DIRS: [(i32, i32); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
impl Solution {
pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
let word: Vec<char> = word.chars().collect();
for r in 0..board.len() {
for c in 0..board[0].len() {
if Self::dfs(&mut board, &word, 0, r, c) {
return true;
}
}
}
false
}
fn dfs(board: &mut Vec<Vec<char>>, word: &[char], idx: usize, row: usize, col: usize) -> bool {
let ch = word[idx];
if ch != board[row][col] {
return false;
}
if idx == word.len() - 1 {
return true;
}
board[row][col] = '#';
for (dr, dc) in DIRS {
let (nr, nc) = (row as i32 + dr, col as i32 + dc);
if nr < 0 || nr >= board.len() as i32 || nc < 0 || nc >= board[0].len() as i32 {
continue;
}
if Self::dfs(board, word, idx + 1, nr as usize, nc as usize) {
board[row][col] = ch; // restore before returning, so the board is unchanged
return true;
}
}
board[row][col] = ch;
false
}
}