struct Solution;
impl Solution {
fn exist(board: Vec<Vec<char>>, word: String) -> bool {
if let Some(mut word_search) = WordSearch::new(board, word) {
word_search.exist()
} else {
false
}
}
}
#[derive(Debug)]
struct WordSearch {
n: usize,
m: usize,
visited: Vec<Vec<bool>>,
board: Vec<Vec<char>>,
word: Vec<char>,
}
impl WordSearch {
fn new(board: Vec<Vec<char>>, word: String) -> Option<Self> {
let n = board.len();
if n == 0 {
return None;
}
let m = board[0].len();
if m == 0 {
return None;
}
if word.is_empty() {
return None;
}
let visited = vec![vec![false; m]; n];
let word = word.chars().collect();
Some(Self {
n,
m,
visited,
board,
word,
})
}
fn dfs(&mut self, i: usize, j: usize, k: usize) -> bool {
if self.visited[i][j] || self.word[k] != self.board[i][j] {
return false;
}
if k == self.word.len() - 1 {
return true;
} else {
self.visited[i][j] = true;
if (j > 0 && self.dfs(i, j - 1, k + 1))
|| (j < self.m - 1 && self.dfs(i, j + 1, k + 1))
|| (i > 0 && self.dfs(i - 1, j, k + 1))
|| (i < self.n - 1 && self.dfs(i + 1, j, k + 1))
{
return true;
}
self.visited[i][j] = false;
}
false
}
fn exist(&mut self) -> bool {
for i in 0..self.n {
for j in 0..self.m {
if self.dfs(i, j, 0) {
return true;
}
}
}
false
}
}
#[test]
fn test() {
let board = vec_vec_char![];
let word = "AC".to_string();
assert_eq!(Solution::exist(board, word), false);
let board = vec_vec_char![['A', 'C'], ['A', 'D']];
let word = "".to_string();
assert_eq!(Solution::exist(board, word), false);
}